oj.uz

답안 #744627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744627 2023-05-18T20:41:28 Z rainboy 원형 문자열 (IZhO13_rowords) C
100 / 100
 127 ms 46456 KB 
/* 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);
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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