# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
564105 |
2022-05-18T14:58:34 Z |
perchuts |
Savez (COCI15_savez) |
C++17 |
|
124 ms |
65536 KB |
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const ll mod = 1e9+7;
const ll base = 101;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<int>qnt;
vector<vector<ll>>hsh, revHsh;
vector<string>v;
ll mul[2000001];
void computeHash(int idx){
int n = qnt[idx];
hsh[idx].pb(ll(v[idx][0]-'A'+1ll));
for(int i=1;i<n;++i){
ll add = hsh[idx].back()*base+ll(v[idx][i]-'A'+1ll);
hsh[idx].pb(add);
hsh[idx].back() %= mod;
}
revHsh[idx].pb(ll(v[idx][n-1]-'A'+1ll));
for(int i=n-2;i>=0;--i){
ll add = revHsh[idx].back()+mul[n-1-i]*ll(v[idx][i]-'A'+1ll);
revHsh[idx].pb(add);
revHsh[idx].back() %= mod;
}
}
unordered_map<int,int>dp;
int main(){_
int n;cin>>n;
v.resize(n), qnt.resize(n);
for(int i=0;i<n;++i){
cin>>v[i];
qnt[i] = sz(v[i]);
}
mul[0] = 1ll;
for(int i=1;i<=2e6;++i)mul[i] = (mul[i-1]*base)%mod;
hsh.resize(n), revHsh.resize(n);
int best = 0;
for(int i=0;i<n;++i){
int idx = i;
computeHash(idx);
int m = qnt[idx], res = 0;
for(int j=0;j<m;++j)if(hsh[idx][j]==revHsh[idx][j])ckmax(res,dp[int(hsh[idx][j])]);
++res;
if(hsh[idx][m-1]==revHsh[idx][m-1])ckmax(dp[int(hsh[idx][m-1])], res);
ckmax(best, res);
}
cout<<best<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15956 KB |
Output is correct |
2 |
Correct |
19 ms |
15912 KB |
Output is correct |
3 |
Correct |
18 ms |
15932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
16044 KB |
Output is correct |
2 |
Correct |
18 ms |
15948 KB |
Output is correct |
3 |
Correct |
20 ms |
17452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
33060 KB |
Output is correct |
2 |
Correct |
61 ms |
33100 KB |
Output is correct |
3 |
Correct |
60 ms |
36580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
17600 KB |
Output is correct |
2 |
Correct |
49 ms |
35312 KB |
Output is correct |
3 |
Correct |
52 ms |
36044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
40336 KB |
Output is correct |
2 |
Correct |
55 ms |
41608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
41420 KB |
Output is correct |
2 |
Correct |
67 ms |
42432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
43796 KB |
Output is correct |
2 |
Correct |
73 ms |
44712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
47432 KB |
Output is correct |
2 |
Correct |
81 ms |
48564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
124 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
108 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |