#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MN = 2010;
int N, M;
string S, T;
int len[MN][MN];
pii par[MN][MN];
int root;
int trace(int r, int c) {
int ret = 0;
while(r != root || c) {
int nr = par[r][c].first;
int nc = par[r][c].second;
r = nr;
c = nc;
ret++;
}
return ret;
}
void reroot() {
int i = root;
int j = 1;
while(j <= M && par[i][j] != pii(i - 1, j - 1)) j++;
if(j > M) return;
while(i < 2 * N && j < M) {
if(par[i + 1][j] == pii(i, j)) {
i++;
par[i][j] = pii(i, j - 1);
}
else if(par[i + 1][j + 1] == pii(i, j)) {
i++;
j++;
par[i][j] = pii(i, j - 1);
}
else j++;
}
while(i < 2 * N && par[i + 1][j] == pii(i, j)) {
i++;
par[i][j] = pii(i, j - 1);
}
}
int main() {
std::ios::sync_with_stdio(false);
cin >> S >> T;
N = S.size();
M = T.size();
for(int i = 0; i <= 2 * N; i++) {
for(int j = 0; j <= M; j++) {
if(!i && !j) continue;
len[i][j] = 1e9;
if(j && len[i][j] > len[i][j - 1] + 1) len[i][j] = len[i][j - 1] + 1, par[i][j] = pii(i, j - 1);
if(i && j && S[(i - 1) % N] == T[j - 1] && len[i][j] > len[i - 1][j - 1] + 1) len[i][j] = len[i - 1][j - 1] + 1, par[i][j] = pii(i - 1, j - 1);
if(i && len[i][j] > len[i - 1][j] + 1) len[i][j] = len[i - 1][j] + 1, par[i][j] = pii(i - 1, j);
}
}
int ans = N + M - trace(N, M);
root = 0;
for(int i = 1; i < N; i++) {
root++;
reroot();
ans = max(ans, N + M - trace(N + i, M));
}
printf("%d", ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Execution timed out |
2067 ms |
504 KB |
Time limit exceeded |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 5 |
Execution timed out |
2058 ms |
1016 KB |
Time limit exceeded |
| 6 |
Correct |
35 ms |
18808 KB |
Output is correct |
| 7 |
Correct |
66 ms |
39852 KB |
Output is correct |
| 8 |
Execution timed out |
2076 ms |
39800 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2070 ms |
39800 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2064 ms |
39800 KB |
Time limit exceeded |
| 11 |
Runtime error |
125 ms |
80760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
136 ms |
82828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
143 ms |
82936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
127 ms |
80888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
142 ms |
84184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
133 ms |
81388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
100 ms |
60408 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
118 ms |
74684 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Execution timed out |
2041 ms |
39800 KB |
Time limit exceeded |
| 20 |
Runtime error |
120 ms |
74872 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 21 |
Runtime error |
77 ms |
40184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
83 ms |
45020 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
99 ms |
49784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 24 |
Runtime error |
88 ms |
49912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 25 |
Runtime error |
96 ms |
54668 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
