#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int Z = 2050;
int N, M;
char S[Z], T[Z];
const int dx[] = { 0, -1, -1 };
const int dy[] = { -1, -1, 0 };
int tb[Z + Z][Z];
int par[Z + Z][Z];
int ans;
int main() {
scanf("%s%s", S + 1, T + 1);
N = strlen(S + 1);
M = strlen(T + 1);
for (int i = N + 1; i <= N + N; i++) S[i] = S[i - N];
memset(par, -1, sizeof par);
for (int i = 1; i <= N + N; i++) par[i][0] = 2;
for (int j = 1; j <= M; j++) par[0][j] = 0;
for (int i = 1; i <= N + N; i++) {
for (int j = 1; j <= M; j++) {
int cands[] = {
tb[i][j - 1],
tb[i - 1][j - 1] + (S[i] == T[j]),
tb[i - 1][j]
};
tb[i][j] = *max_element(cands, cands + 3);
par[i][j] = max_element(cands, cands + 3) - cands;
}
}
for (int r = 1; r <= N; r++) {
// drop the first row
{
int i = r;
int j;
for (j = 1; j <= M && par[r][j] != 1; j++);
if (j <= M) {
par[i][j] = 0;
while (i < N + N && j <= M) {
if (par[i + 1][j] == 2) ++i;
else if (j == M) break;
else if (par[i + 1][j + 1] == 1) ++i, ++j;
else ++j;
par[i][j] = 0;
}
}
}
// calc answer
{
int ret = 0;
for (int i = N + r, j = M; i > r && j > 0;) {
int d = par[i][j];
if (d == 1) ++ret;
i += dx[d]; j += dy[d];
}
ans = max(ans, ret);
printf("%d %d\n", r, ret);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
rowords.cpp: In function 'int main()':
rowords.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%s", S + 1, T + 1);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
33272 KB |
Output isn't correct |
2 |
Incorrect |
30 ms |
33296 KB |
Output isn't correct |
3 |
Incorrect |
29 ms |
33400 KB |
Output isn't correct |
4 |
Incorrect |
30 ms |
33656 KB |
Output isn't correct |
5 |
Incorrect |
30 ms |
33528 KB |
Output isn't correct |
6 |
Incorrect |
51 ms |
41976 KB |
Output isn't correct |
7 |
Incorrect |
63 ms |
49016 KB |
Output isn't correct |
8 |
Incorrect |
111 ms |
48988 KB |
Output isn't correct |
9 |
Incorrect |
117 ms |
49016 KB |
Output isn't correct |
10 |
Incorrect |
105 ms |
49016 KB |
Output isn't correct |
11 |
Runtime error |
134 ms |
102180 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Runtime error |
134 ms |
105976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
13 |
Runtime error |
142 ms |
105972 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
14 |
Runtime error |
136 ms |
103544 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
15 |
Runtime error |
141 ms |
107036 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
16 |
Runtime error |
134 ms |
101880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
17 |
Runtime error |
145 ms |
103160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
18 |
Runtime error |
151 ms |
111864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
19 |
Incorrect |
95 ms |
49108 KB |
Output isn't correct |
20 |
Runtime error |
146 ms |
107444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
21 |
Runtime error |
144 ms |
98800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Runtime error |
151 ms |
103416 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
23 |
Runtime error |
158 ms |
106436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
24 |
Runtime error |
158 ms |
108788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
25 |
Runtime error |
167 ms |
113228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |