東京大学プログラミングコンテスト2014

Submission #7419444

Source codeソースコード

#include <iostream>
#include <map>
#include <vector>
using namespace std;
using i64 = int64_t;

class Trie {
  struct Node {
    i64 val, maxi; // maxi: 子供の最大値
    map<int, Node*> children;
    Node() : val(0), maxi(0) {}
    ~Node() { for(auto &kv : children) { delete kv.second; } }
    i64 insert(int x, int y) {
      if(x == 0) {
        val += y;
        return val + maxi;
      }
      Node **nxt = &(children[x % 10]);
      if(*nxt == nullptr) { *nxt = new Node; }
      maxi = max(maxi, (*nxt)->insert(x / 10, y));
      return val + maxi;
    }
  };
  Node *root;
 public:
  Trie() { root = new Node; }
  ~Trie() { delete root; }
  i64 insert(int x, int y) { return root->insert(x, y); }
};

int main(void) {
  int N; scanf("%d", &N);
  Trie tree;
  for(int i=0; i<N; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    i64 res = tree.insert(a, b);
    printf("%ld\n", res);
  }
  return 0;
}

Submission

Task問題 E - 宝くじ
User nameユーザ名 asc
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 200
Source lengthソースコード長 953 Byte
File nameファイル名
Exec time実行時間 225 ms
Memory usageメモリ使用量 73088 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:32:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int N; scanf("%d", &N);
^
./Main.cpp:35:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
^

Test case

Set

Set name Score得点 / Max score Cases
All 200 / 200 scrambled_00.txt,scrambled_01.txt,scrambled_02.txt,scrambled_03.txt,scrambled_04.txt,scrambled_05.txt,scrambled_06.txt,scrambled_07.txt,scrambled_08.txt,scrambled_09.txt,scrambled_10.txt,scrambled_11.txt,scrambled_12.txt,scrambled_13.txt,scrambled_14.txt,scrambled_15.txt,scrambled_16.txt,scrambled_17.txt,scrambled_18.txt,scrambled_19.txt,scrambled_20.txt,scrambled_21.txt,scrambled_22.txt,scrambled_23.txt,scrambled_24.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
scrambled_00.txt AC 1 ms 256 KB
scrambled_01.txt AC 1 ms 256 KB
scrambled_02.txt AC 41 ms 1664 KB
scrambled_03.txt AC 36 ms 1536 KB
scrambled_04.txt AC 41 ms 1664 KB
scrambled_05.txt AC 28 ms 1152 KB
scrambled_06.txt AC 33 ms 1280 KB
scrambled_07.txt AC 11 ms 512 KB
scrambled_08.txt AC 18 ms 768 KB
scrambled_09.txt AC 37 ms 1664 KB
scrambled_10.txt AC 32 ms 1408 KB
scrambled_11.txt AC 11 ms 640 KB
scrambled_12.txt AC 31 ms 1408 KB
scrambled_13.txt AC 8 ms 512 KB
scrambled_14.txt AC 108 ms 30976 KB
scrambled_15.txt AC 5 ms 1792 KB
scrambled_16.txt AC 105 ms 29952 KB
scrambled_17.txt AC 15 ms 5504 KB
scrambled_18.txt AC 98 ms 28672 KB
scrambled_19.txt AC 210 ms 73088 KB
scrambled_20.txt AC 225 ms 65408 KB
scrambled_21.txt AC 140 ms 43008 KB
scrambled_22.txt AC 140 ms 42752 KB
scrambled_23.txt AC 24 ms 10368 KB
scrambled_24.txt AC 52 ms 20480 KB