/// You just can't beat the person who never gives up
/// ICPC next year
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std ;
const int N = 5e5+5 ,M = 3e6+5 ;
typedef unsigned long long ull ;
const int base = 29 ;
int mod[2] = {1000055423 ,1001337299};
struct rabinKarp{
int val[2] ;
rabinKarp(){
memset(val,0,sizeof val);
}
void push_back(int x){
for(int i=0;i<2;++i){
val[i] = (1ll * val[i] * base) %mod[i] + x;
while(val[i]>=mod[i]) val[i] -= mod[i] ;
}
}
ull hashVal(){
return (ull)val[0] * 1e10 + val[1] ;
}
};
int n ;
char str[M] ;
vector<ull> h[N] ;
int cnt[M] ;
bool is[M] ;
void compress(){
map<ull,int> mp ;
for(int i=0;i<n;++i) for(auto go:h[i]) mp[go] ;
int v = 0 ;
for(auto&go:mp) go.second = v++ ;
for(int i=0;i<n;++i) for(int j=0;j<h[i].size();++j) h[i][j] = mp[h[i][j]] ;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%s",str);
int m = strlen(str);
reverse(str,str+m) ;
rabinKarp rbk ;
h[i].push_back(0);
for(int j=0;j<m;++j){
rbk.push_back(str[j]-'a'+1);
h[i].push_back(rbk.hashVal());
}
}
compress() ;
for(int i=0;i<n;++i){
++cnt[h[i][h[i].size()-2]] ;
is[h[i].back()] = 1 ;
}
int ans = 0 ;
for(int i=0;i<n;++i){
int cur = 0 ;
while(h[i].size()>=2 && is[h[i].back()]){
cur += cnt[h[i][h[i].size()-2]] ;
h[i].pop_back();
}
ans = max(ans ,cur);
}
printf("%d",ans);
return 0;
}
Compilation message
rima.cpp: In function 'void compress()':
rima.cpp:40:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<n;++i) for(int j=0;j<h[i].size();++j) h[i][j] = mp[h[i][j]] ;
~^~~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
rima.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",str);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12032 KB |
Output is correct |
| 3 |
Correct |
11 ms |
12160 KB |
Output is correct |
| 4 |
Execution timed out |
1102 ms |
89052 KB |
Time limit exceeded |
| 5 |
Correct |
526 ms |
41208 KB |
Output is correct |
| 6 |
Incorrect |
574 ms |
38716 KB |
Output isn't correct |
| 7 |
Incorrect |
521 ms |
36708 KB |
Output isn't correct |
| 8 |
Incorrect |
501 ms |
36316 KB |
Output isn't correct |
| 9 |
Execution timed out |
1092 ms |
65756 KB |
Time limit exceeded |
| 10 |
Incorrect |
519 ms |
36068 KB |
Output isn't correct |
