Submission #100662

#	Time	Username	Problem	Language	Result	Execution time	Memory
100662		ainta	Round words (IZhO13_rowords)	C++17	40 / 100	118 ms	54264 KiB

rowords

#include<cstdio>
#include<algorithm>
using namespace std;
char p[4010], q[2010];
int n, m, D[4010][2010];
int dir[4010][2010], res;
bool OK[4010][2010];
void Do() {
	int i, j;
	for (i = 1; i <= n; i++)p[i + n] = p[i];
	for (i = 0; i <= n + n; i++) {
		for (j = 0; j <= m; j++) {
			dir[i][j] = D[i][j] = 0;
			if (i&&j) {
				if (p[i] == q[j])OK[i][j] = true;
				else OK[i][j] = false;
			}
		}
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= m; j++) {
			if (i == 0 && j == 0)continue;
			if (i == 0) continue;
			if (j == 0) {
				dir[i][j] = 2;
				continue;
			}
			D[i][j] = D[i][j - 1];
			if (OK[i][j] && D[i][j] < D[i - 1][j - 1] + 1) {
				D[i][j] = D[i - 1][j - 1] + 1, dir[i][j] = 1;
			}
			if (D[i][j] < D[i - 1][j]) {
				D[i][j] = D[i - 1][j], dir[i][j] = 2;
			}
		}
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (dir[i][j]) {
				break;
			}
		}
		if (j != m + 1) {
			int x = i, y = j;
			dir[x][y] = 0;
			while (x < i + n - 1 && y <= m) {
				if (dir[x + 1][y] == 2) {
					x++;
					dir[x][y] = 0;
				}
				else if (dir[x + 1][y + 1] == 1) {
					x++, y++;
					dir[x + 1][y + 1] = 0;
				}
				else y++;
			}
			if (y <= m) {
				for (j = y; j <= m; j++)D[i + n - 1][j]--;
			}
		}
		for (j = 0; j <= m; j++) {
			if (j == 0) {
				dir[i + n][j] = 2;
				D[i + n][j] = D[i + n - 1][j];
				continue;
			}
			D[i + n][j] = D[i + n][j - 1];
			if (OK[i + n][j] && D[i + n][j] < D[i + n - 1][j - 1] + 1)D[i + n][j] = D[i + n - 1][j - 1] + 1, dir[i + n][j] = 1;
			if (D[i + n][j] < D[i + n - 1][j])D[i + n][j] = D[i + n - 1][j], dir[i + n][j] = 2;
		}
		res = max(res, D[i + n][m]);
	}
}
int main() {
	scanf("%s%s", p + 1, q + 1);
	int i;
	for (i = 1; p[i]; i++);
	n = i - 1;
	for (i = 1; q[i]; i++);
	m = i - 1;
	Do();
	reverse(p + 1, p + n + 1);
	Do();
	printf("%d\n", res);
}

Compilation message (stderr)

rowords.cpp: In function 'int main()':
rowords.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", p + 1, q + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100