oj.uz

답안 #100655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100655 2019-03-13T05:39:19 Z ainta 원형 문자열 (IZhO13_rowords) C++17
32 / 100
 84 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];
bool OK[4010][2010];
int main() {
	int i, j;
	scanf("%s%s", p + 1, q + 1);
	for (i = 1; p[i]; i++);
	n = i - 1;
	for (i = 1; q[i]; i++);
	m = i - 1;
	for (i = 1; i <= n; i++)p[i + n] = p[i];
	for (i = 1; i <= n+n; i++) {
		for (j = 1; j <= m; j++) {
			if (p[i] == q[j])OK[i][j] = true;
		}
	}
	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;
			}
		}
	}
	int res = 0;
	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]);
	}
	printf("%d\n", res);
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:10: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
32.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Incorrect 3 ms 1144 KB Output isn't correct
6 Correct 22 ms 21880 KB Output is correct
7 Correct 31 ms 24036 KB Output is correct
8 Incorrect 60 ms 34680 KB Output isn't correct
9 Incorrect 60 ms 35292 KB Output isn't correct
10 Incorrect 58 ms 35672 KB Output isn't correct
11 Incorrect 58 ms 39160 KB Output isn't correct
12 Correct 51 ms 40940 KB Output is correct
13 Incorrect 84 ms 42488 KB Output isn't correct
14 Incorrect 71 ms 40564 KB Output isn't correct
15 Incorrect 67 ms 44024 KB Output isn't correct
16 Incorrect 68 ms 37752 KB Output isn't correct
17 Incorrect 58 ms 42104 KB Output isn't correct
18 Incorrect 77 ms 50540 KB Output isn't correct
19 Incorrect 52 ms 35576 KB Output isn't correct
20 Incorrect 83 ms 45000 KB Output isn't correct
21 Correct 41 ms 38264 KB Output is correct
22 Correct 59 ms 43256 KB Output is correct
23 Incorrect 64 ms 46128 KB Output isn't correct
24 Incorrect 69 ms 48696 KB Output isn't correct
25 Incorrect 81 ms 54264 KB Output isn't correct