Submission #100662

# Submission time Handle Problem Language Result Execution time Memory
100662 2019-03-13T05:47:48 Z ainta Round words (IZhO13_rowords) C++17
40 / 100
118 ms 54264 KB
#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

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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Incorrect 3 ms 1144 KB Output isn't correct
6 Correct 25 ms 21888 KB Output is correct
7 Correct 50 ms 35788 KB Output is correct
8 Incorrect 96 ms 35704 KB Output isn't correct
9 Incorrect 94 ms 35808 KB Output isn't correct
10 Incorrect 85 ms 35704 KB Output isn't correct
11 Incorrect 98 ms 39288 KB Output isn't correct
12 Correct 83 ms 42744 KB Output is correct
13 Incorrect 117 ms 42856 KB Output isn't correct
14 Incorrect 97 ms 40696 KB Output isn't correct
15 Incorrect 107 ms 44140 KB Output isn't correct
16 Incorrect 108 ms 38648 KB Output isn't correct
17 Incorrect 81 ms 42252 KB Output isn't correct
18 Incorrect 114 ms 50808 KB Output isn't correct
19 Incorrect 78 ms 35704 KB Output isn't correct
20 Incorrect 118 ms 45304 KB Output isn't correct
21 Correct 52 ms 38260 KB Output is correct
22 Correct 70 ms 43388 KB Output is correct
23 Incorrect 80 ms 46200 KB Output isn't correct
24 Correct 84 ms 48760 KB Output is correct
25 Incorrect 100 ms 54264 KB Output isn't correct