Submission #98819

#TimeUsernameProblemLanguageResultExecution timeMemory
98819someone_aaSavez (COCI15_savez)C++17
48 / 120
92 ms20220 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 510; const ll mod = 468395662504823; const ll k = 37; int dp[maxn], n; vector<ll>pref[maxn]; vector<ll>suff[maxn]; string codes; int sz[maxn]; bool match(int i, int j) { // returns true if we can put string i at string j if(sz[i] > sz[j]) return false; if(pref[j][sz[i]] == pref[i][sz[i]] && suff[j][sz[i]] == suff[i][sz[i]]) return true; return false; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>codes; sz[i] = codes.length(); pref[i].pb(0); ll kk = 1LL; for(int j=0;j<codes.length();j++) { ll curr = pref[i].back() + (kk * (codes[j] - 'A' + 1))%mod; curr %= mod; kk *= k; kk %= mod; pref[i].pb(curr); } kk = 1LL; suff[i].pb(0); for(int j=codes.length()-1;j>=0;j--) { ll curr = suff[i].back() + (kk * (codes[j] - 'A' + 1))%mod; curr %= mod; kk *= k; kk %= mod; suff[i].pb(curr); } } int result = 0; for(int i=1;i<=n;i++) { dp[i] = 1; for(int j=1;j<i;j++) { if(match(j, i)) { dp[i] = max(dp[i], dp[j] + 1); } } result = max(result ,dp[i]); } cout<<result<<"\n"; return 0; }

Compilation message (stderr)

savez.cpp: In function 'int main()':
savez.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<codes.length();j++) {
                     ~^~~~~~~~~~~~~~~
#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...