# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
98787 | 2019-02-25T21:40:33 Z | someone_aa | Savez (COCI15_savez) | C++17 | 82 ms | 21624 KB |
#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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 10 ms | 1920 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 58 ms | 19344 KB | Output is correct |
2 | Correct | 64 ms | 19412 KB | Output is correct |
3 | Correct | 65 ms | 21624 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 2176 KB | Output is correct |
2 | Correct | 68 ms | 20952 KB | Output is correct |
3 | Correct | 82 ms | 21496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 9 ms | 3840 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 6 ms | 1920 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 1280 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 0 ms | 896 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 768 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 640 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |