Submission #6896735
Source Code Expand
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) v.erase(unique(ALL(v)), v.end())
#define bit(i) (1LL<<i)
#define sz(v) ((LLI)(v).size())
#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif
#define gcd __gcd
using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}
template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> istream& operator>>(istream &is, pair<T,U> &p){is >> p.first >> p.second; return is;}
template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <int N> class Trie{
public:
int table[N];
struct node{
LLI val;
LLI sum = 0;
node *ch[N] = {};
node(LLI val): val(val){}
node(): val(0){}
};
Trie(const string &s){
REP(i,(int)s.size()){
table[(int)s[i]] = i;
}
}
node *root = nullptr;
node* insert(node *t, const string &s, LLI val, int i){
if(!t) t = new node();
if(i >= (int)s.size()){
t->val += val;
LLI x = 0;
REP(i,N){
if(t->ch[i]) chmax(x, t->ch[i]->sum);
}
t->sum = x+t->val;
return t;
}
int c = table[(int)s[i]];
t->ch[c] = insert(t->ch[c], s, val, i+1);
LLI x = 0;
REP(i,N){
if(t->ch[i]) chmax(x, t->ch[i]->sum);
}
t->sum = x+t->val;
return t;
}
void insert(const string &s, LLI val){
root = insert(root, s, val, 0);
}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N;
while(cin >> N){
Trie<10> trie("0123456789");
REP(i,N){
string a; cin >> a;
LLI b; cin >> b;
reverse(ALL(a));
trie.insert(a,b);
cout << trie.root->sum << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - 宝くじ |
User |
you070707 |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2865 Byte |
Status |
AC |
Exec Time |
330 ms |
Memory |
57088 KB |
Judge Result
Set Name |
All |
Score / Max Score |
200 / 200 |
Status |
|
Set Name |
Test Cases |
All |
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 |
Case Name |
Status |
Exec Time |
Memory |
scrambled_00.txt |
AC |
1 ms |
256 KB |
scrambled_01.txt |
AC |
1 ms |
256 KB |
scrambled_02.txt |
AC |
234 ms |
1664 KB |
scrambled_03.txt |
AC |
205 ms |
1536 KB |
scrambled_04.txt |
AC |
232 ms |
1664 KB |
scrambled_05.txt |
AC |
156 ms |
1152 KB |
scrambled_06.txt |
AC |
179 ms |
1280 KB |
scrambled_07.txt |
AC |
57 ms |
640 KB |
scrambled_08.txt |
AC |
99 ms |
896 KB |
scrambled_09.txt |
AC |
223 ms |
1664 KB |
scrambled_10.txt |
AC |
192 ms |
1536 KB |
scrambled_11.txt |
AC |
61 ms |
640 KB |
scrambled_12.txt |
AC |
191 ms |
1408 KB |
scrambled_13.txt |
AC |
45 ms |
512 KB |
scrambled_14.txt |
AC |
267 ms |
24448 KB |
scrambled_15.txt |
AC |
12 ms |
1536 KB |
scrambled_16.txt |
AC |
259 ms |
23680 KB |
scrambled_17.txt |
AC |
39 ms |
4352 KB |
scrambled_18.txt |
AC |
241 ms |
22656 KB |
scrambled_19.txt |
AC |
320 ms |
57088 KB |
scrambled_20.txt |
AC |
330 ms |
51200 KB |
scrambled_21.txt |
AC |
210 ms |
33664 KB |
scrambled_22.txt |
AC |
205 ms |
33408 KB |
scrambled_23.txt |
AC |
43 ms |
8192 KB |
scrambled_24.txt |
AC |
93 ms |
16128 KB |