oj.uz

Submission #13622

# Submission time Handle Problem Language Result Execution time Memory
13622 2015-02-25T13:21:29 Z tncks0121 Round words (IZhO13_rowords) C++14
44 / 100
 343 ms 56128 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int Z = 2050;

int N, M;
char S[Z + Z], T[Z];

const int dx[] = { 0, -1, -1 };
const int dy[] = { -1, -1, 0 };

int tb[Z + Z][Z];
int par[Z + Z][Z];

int ans;

void solve() {
	for (int i = N + 1; i <= N + N; i++) S[i] = S[i - N];

	memset(par, -1, sizeof par);

	for (int i = 1; i <= N + N; i++) par[i][0] = 2;
	for (int j = 1; j <= M; j++) par[0][j] = 0;
	for (int i = 1; i <= N + N; i++) {
		for (int j = 1; j <= M; j++) {
			int cands[] = {
				tb[i][j - 1],
				tb[i - 1][j - 1] + (S[i] == T[j]),
				tb[i - 1][j]
			};
			tb[i][j] = *max_element(cands, cands + 3);
			par[i][j] = max_element(cands, cands + 3) - cands;
		}
	}

	ans = max(ans, tb[N][M]);
	for (int r = 1; r <= N; r++) {
		// drop the first row
			{
				int i = r;
				int j;
				for (j = 1; j <= M && par[r][j] != 1; j++);
				if (j <= M) {
					par[i][j] = 0;

					while (i < N + N && j <= M) {
						if (par[i + 1][j] == 2) ++i;
						else if (j == M) break;
						else if (par[i + 1][j + 1] == 1) ++i, ++j;
						else ++j;
						par[i][j] = 0;
					}
				}
			}

		// calc answer
		{
			int ret = 0;
			for (int i = N + r, j = M; i > r && j > 0;) {
				int d = par[i][j];
				if (d == 1) ++ret;
				i += dx[d]; j += dy[d];
			}
			ans = max(ans, ret);
		}
	}
}

int main() {
	scanf("%s%s", S + 1, T + 1);
	N = strlen(S + 1);
	M = strlen(T + 1);

	solve();
	reverse(T + 1, T + M + 1);
	solve();

	printf("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
44.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 33272 KB Output is correct
2 Correct 36 ms 33272 KB Output is correct
3 Correct 35 ms 33400 KB Output is correct
4 Correct 36 ms 33572 KB Output is correct
5 Incorrect 37 ms 33528 KB Output isn't correct
6 Correct 65 ms 42104 KB Output is correct
7 Correct 86 ms 49204 KB Output is correct
8 Incorrect 178 ms 49084 KB Output isn't correct
9 Incorrect 168 ms 49016 KB Output isn't correct
10 Incorrect 156 ms 49088 KB Output isn't correct
11 Incorrect 169 ms 50640 KB Output isn't correct
12 Correct 184 ms 52584 KB Output is correct
13 Incorrect 213 ms 52444 KB Output isn't correct
14 Incorrect 185 ms 51448 KB Output isn't correct
15 Incorrect 280 ms 53084 KB Output isn't correct
16 Incorrect 191 ms 50556 KB Output isn't correct
17 Incorrect 211 ms 51048 KB Output isn't correct
18 Correct 249 ms 55524 KB Output is correct
19 Incorrect 148 ms 49016 KB Output isn't correct
20 Incorrect 232 ms 53160 KB Output isn't correct
21 Correct 177 ms 48996 KB Output is correct
22 Correct 232 ms 51256 KB Output is correct
23 Incorrect 270 ms 52600 KB Output isn't correct
24 Correct 280 ms 53880 KB Output is correct
25 Incorrect 343 ms 56128 KB Output isn't correct