제출 #1028078

#제출 시각아이디문제언어결과실행 시간메모리
1028078earlyamazonSavez (COCI15_savez)C++14
108 / 120
2203 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int mn = 5e5+7; const int mod1 = 1e9+7; const int mod2 = 1e9+9; const int p1 = 269; const int p2 = 271; int32_t n,wyn; string t[mn]; vector<int> hpref[mn]; map<int32_t, int32_t> dp; int pot[mn]; int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(); cin>>n; pot[0] = 1; for (int i = 1; i < mn; i++){ pot[i] = pot[i-1]*p1%mod1; } for (int i = 0; i < n; i++){ cin>>t[i]; hpref[i].resize(t[i].size()+1); hpref[i][0] = 0; for (int j = 1; j <= (int)t[i].size(); j++){ hpref[i][j] = (hpref[i][j-1]*p1+t[i][j-1])%mod1; } int32_t mx = 0; for (int j = 1; j <= (int)t[i].size(); j++){ int h = hpref[i][j]; if (h == (hpref[i][t[i].size()]-((hpref[i][t[i].size()-j]*pot[j])%mod1)+mod1)%mod1){ mx = max(mx, dp[h]); } } mx++; wyn = max(wyn, mx); dp[hpref[i].back()] = mx; // cout<<hpref[i].size()<<" "<<hpref[i].back().first<<" "<<hpref[i].back().second<<" "<<mx<<"\n"; } cout<<wyn<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...