/// 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 = 3e6+5 ;
int n ,m ,sz ;
vector<pair<int,int>> to[N] ;
char str[N] ;
bool en[N] ;
void insert_str(){
int cur = 0 ;
for(int i=0;i<m;++i){
int cc = str[i] - 'a' ;
int j = 0 ;
while(j<to[cur].size() && to[cur][j].first!=cc) ++j ;
if(j==to[cur].size()) to[cur].push_back({cc ,++sz}) ;
cur = to[cur][j].second ;
}
en[cur] = 1 ;
}
int mem[N][2][2] ;
int dfs(int cur,bool is,bool ok){
int&ret = mem[cur][is][ok];
if(~ret) return ret;
ret = 0 ;
int here = 0 ;
for(auto i:to[cur]) here += en[i.second] ;
if(!is){
for(auto i:to[cur]){
ret = max(ret ,dfs(i.second,0,0));
if(en[i.second]) ret = max(ret ,1+dfs(i.second,1,0));
}
vector<int> v ;
for(auto i:to[cur]) if(en[i.second]){
v.push_back(dfs(i.second,1,1));
sort(v.rbegin(),v.rend());
if(v.size()>2) v.pop_back();
}
int s = 0 ;
for(int i:v) s += i ;
return ret = max(ret ,here + s) ; ;
}
if(is && !ok){
vector<int> v ;
for(auto i:to[cur]) if(en[i.second]){
v.push_back(dfs(i.second,1,1));
sort(v.rbegin(),v.rend());
if(v.size()>2) v.pop_back();
}
int s = 0 ;
for(int i:v) s += i ;
ret = max(ret ,here + s);
return ret ;
}
if(!here) return ret ;
ret = max(ret,here) ;
for(auto i:to[cur]) if(en[i.second]) ret = max(ret ,here + dfs(i.second,1,1)) ;
return ret ;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%s",str);
m = strlen(str) ;
reverse(str,str+m);
insert_str();
}
memset(mem,-1,sizeof mem);
printf("%d",dfs(0,0,0));
return 0;
}
Compilation message
rima.cpp: In function 'void insert_str()':
rima.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<to[cur].size() && to[cur][j].first!=cc) ++j ;
~^~~~~~~~~~~~~~~
rima.cpp:21:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j==to[cur].size()) to[cur].push_back({cc ,++sz}) ;
~^~~~~~~~~~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
rima.cpp:69: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 |
71 ms |
117752 KB |
Output is correct |
| 2 |
Correct |
69 ms |
117752 KB |
Output is correct |
| 3 |
Correct |
67 ms |
117624 KB |
Output is correct |
| 4 |
Correct |
484 ms |
132472 KB |
Output is correct |
| 5 |
Correct |
96 ms |
120312 KB |
Output is correct |
| 6 |
Correct |
116 ms |
170360 KB |
Output is correct |
| 7 |
Correct |
118 ms |
170300 KB |
Output is correct |
| 8 |
Correct |
124 ms |
170104 KB |
Output is correct |
| 9 |
Correct |
150 ms |
172464 KB |
Output is correct |
| 10 |
Correct |
121 ms |
170264 KB |
Output is correct |
