Submission #5723309
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);}
class Trie{
public:
vector<unordered_map<char,int>> trie;
int n;
public:
Trie(): trie(1), n(1){}
void add(const string &s){
int cur = 0;
REP(i,(int)s.size()){
if(EXIST(trie[cur],s[i])){
cur = trie[cur][s[i]];
}else{
++n;
trie.resize(n);
trie[cur][s[i]] = n-1;
cur = trie[cur][s[i]];
}
}
}
bool _query(int cur, int i, const string &s, const function<void(int,int,const vector<unordered_map<char,int>>&)> &f){
if(i >= (int)s.size()){
f(cur, i, trie);
return true;
}
if(EXIST(trie[cur], s[i])){
bool ret = _query(trie[cur][s[i]], i+1, s, f);
if(ret){
f(cur, i, trie);
}
return ret;
}else{
return false;
}
}
bool query(const string &s, const function<void(int,int,const vector<unordered_map<char,int>>&)> &f){
return _query(0, 0, s, f);
}
int size(){
return n;
}
};
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N;
while(cin >> N){
Trie trie;
vector<LLI> d(N*20);
vector<LLI> s(N*20);
LLI ans = 0;
REP(i,N){
string a; cin >> a;
LLI b; cin >> b;
sort(ALL(a));
trie.add(a);
auto f =
[&](int c, int k, const vector<unordered_map<char,int>> &t){
if(k==(int)a.size()){
s[c] += b;
}
chmax(d[c], s[c]);
for(auto &p : t[c]){
chmax(d[c], d[p.snd]+s[c]);
}
};
trie.query(a, f);
dump(d);
dump(s);
chmax(ans, d[0]);
cout << ans << endl;
}
dump(trie.trie);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - 宝くじ |
User |
you070707 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3259 Byte |
Status |
WA |
Exec Time |
382 ms |
Memory |
39248 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
6 ms |
896 KB |
scrambled_01.txt |
AC |
1 ms |
256 KB |
scrambled_02.txt |
AC |
293 ms |
33024 KB |
scrambled_03.txt |
AC |
271 ms |
28928 KB |
scrambled_04.txt |
AC |
295 ms |
32896 KB |
scrambled_05.txt |
AC |
203 ms |
22016 KB |
scrambled_06.txt |
AC |
235 ms |
25728 KB |
scrambled_07.txt |
AC |
73 ms |
8064 KB |
scrambled_08.txt |
AC |
124 ms |
13952 KB |
scrambled_09.txt |
AC |
261 ms |
33024 KB |
scrambled_10.txt |
AC |
225 ms |
27904 KB |
scrambled_11.txt |
AC |
73 ms |
8960 KB |
scrambled_12.txt |
AC |
222 ms |
27136 KB |
scrambled_13.txt |
AC |
54 ms |
6528 KB |
scrambled_14.txt |
WA |
325 ms |
38996 KB |
scrambled_15.txt |
WA |
15 ms |
2332 KB |
scrambled_16.txt |
WA |
299 ms |
37844 KB |
scrambled_17.txt |
WA |
48 ms |
6616 KB |
scrambled_18.txt |
WA |
285 ms |
36436 KB |
scrambled_19.txt |
WA |
305 ms |
33024 KB |
scrambled_20.txt |
WA |
382 ms |
39248 KB |
scrambled_21.txt |
WA |
248 ms |
26580 KB |
scrambled_22.txt |
WA |
243 ms |
26324 KB |
scrambled_23.txt |
WA |
57 ms |
7252 KB |
scrambled_24.txt |
WA |
113 ms |
15956 KB |