# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
98787 | someone_aa | Savez (COCI15_savez) | C++17 | 82 ms | 21624 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[maxn];
bool match(int i, int j) {
// returns true if we can put string i at string j
if(codes[i].length() > codes[j].length()) return false;
if(pref[j][codes[i].length()] == pref[i][codes[i].length()] && suff[j][codes[i].length()] == suff[i][codes[i].length()]) return true;
return false;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>codes[i];
pref[i].pb(0);
ll kk = 1LL;
for(int j=0;j<codes[i].length();j++) {
ll curr = pref[i].back() + (kk * (codes[i][j] - 'A' + 1))%mod;
curr %= mod;
kk *= k;
kk %= mod;
pref[i].pb(curr);
}
kk = 1LL;
suff[i].pb(0);
for(int j=codes[i].length()-1;j>=0;j--) {
ll curr = suff[i].back() + (kk * (codes[i][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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |