Submission #744627

#	Time	Username	Problem	Language	Result	Execution time	Memory
744627		rainboy	Round words (IZhO13_rowords)	C11	100 / 100	127 ms	46456 KiB

rowords

/* 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 (stderr)

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 / 100