/* https://codeforces.com/blog/entry/21372 */
/* https://arxiv.org/pdf/1208.0396.pdf */
/* https://oj.uz/submission/314177 (Benq) */
#include <stdio.h>
#include <string.h>
#define N 2000
#define M 2000
int max(int a, int b) { return a > b ? a : b; }
int solve(char *aa, int n, char *bb, int m) {
static int dp[N * 2 + 1][M + 1], dir[N * 2 + 1][M + 1];
int l, i, j, x, ans;
for (i = 0; i <= n * 2; i++)
for (j = 0; j <= m; j++)
if (i == 0 && j == 0)
dp[i][j] = 0, dir[i][j] = -1;
else {
dp[i][j] = dir[i][j] = -1;
if (j > 0 && dp[i][j] < (x = dp[i][j - 1]))
dp[i][j] = x, dir[i][j] = 0;
if (i > 0 && j > 0 && aa[(i - 1) % n] == bb[j - 1] && dp[i][j] < (x = dp[i - 1][j - 1] + 1))
dp[i][j] = x, dir[i][j] = 1;
if (i > 0 && dp[i][j] < (x = dp[i - 1][j]))
dp[i][j] = x, dir[i][j] = 2;
}
ans = 0;
for (l = 0; l < n; l++) {
i = n + l, j = m, x = 0;
while (dir[i][j] != -1)
if (dir[i][j] == 0)
j--;
else if (dir[i][j] == 1)
i--, j--, x++;
else
i--;
ans = max(ans, x);
i = l + 1, j = 0;
dir[i][j] = -1;
while (j < m)
if (dir[i][j + 1] == 0)
j++;
else {
dir[i][j + 1] = 0;
if (i++ == n * 2)
break;
if (dir[i][j + 1] == 1)
j++;
}
}
return ans;
}
int main() {
static char aa[N + 1], bb[M + 1];
int n, m, i, j, ans, tmp;
scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
ans = solve(aa, n, bb, m);
for (i = 0, j = n - 1; i < j; i++, j--)
tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
ans = max(ans, solve(aa, n, bb, m));
printf("%d\n", ans);
return 0;
}
Compilation message
rowords.c: In function 'main':
rowords.c:60:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
0 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
17 ms |
17876 KB |
Output is correct |
| 7 |
Correct |
41 ms |
31620 KB |
Output is correct |
| 8 |
Correct |
86 ms |
31624 KB |
Output is correct |
| 9 |
Correct |
89 ms |
31620 KB |
Output is correct |
| 10 |
Correct |
81 ms |
31524 KB |
Output is correct |
| 11 |
Correct |
81 ms |
34768 KB |
Output is correct |
| 12 |
Correct |
69 ms |
37816 KB |
Output is correct |
| 13 |
Correct |
113 ms |
37884 KB |
Output is correct |
| 14 |
Correct |
96 ms |
36044 KB |
Output is correct |
| 15 |
Correct |
98 ms |
39012 KB |
Output is correct |
| 16 |
Correct |
104 ms |
34060 KB |
Output is correct |
| 17 |
Correct |
79 ms |
36428 KB |
Output is correct |
| 18 |
Correct |
122 ms |
44764 KB |
Output is correct |
| 19 |
Correct |
69 ms |
31644 KB |
Output is correct |
| 20 |
Correct |
125 ms |
39944 KB |
Output is correct |
| 21 |
Correct |
67 ms |
31572 KB |
Output is correct |
| 22 |
Correct |
90 ms |
36228 KB |
Output is correct |
| 23 |
Correct |
97 ms |
39040 KB |
Output is correct |
| 24 |
Correct |
111 ms |
41188 KB |
Output is correct |
| 25 |
Correct |
127 ms |
46456 KB |
Output is correct |
