oj.uz

Submission #13623

# Submission time Handle Problem Language Result Execution time Memory
13623 2015-02-25T13:32:13 Z tncks0121 Round words (IZhO13_rowords) C++14
100 / 100
 389 ms 96348 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 = 3050;

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) par[++i][j] = 0;
					else if (j == M) break;
					else if (par[i + 1][j + 1] == 1) par[++i][++j] = 0;
					else ++j;
				}
			}
		}

		// 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:98: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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 73208 KB Output is correct
2 Correct 75 ms 73208 KB Output is correct
3 Correct 76 ms 73348 KB Output is correct
4 Correct 79 ms 73592 KB Output is correct
5 Correct 77 ms 73420 KB Output is correct
6 Correct 107 ms 82040 KB Output is correct
7 Correct 126 ms 88952 KB Output is correct
8 Correct 199 ms 89116 KB Output is correct
9 Correct 200 ms 88952 KB Output is correct
10 Correct 190 ms 89028 KB Output is correct
11 Correct 199 ms 90668 KB Output is correct
12 Correct 185 ms 92856 KB Output is correct
13 Correct 256 ms 92804 KB Output is correct
14 Correct 240 ms 91244 KB Output is correct
15 Correct 262 ms 93816 KB Output is correct
16 Correct 227 ms 90360 KB Output is correct
17 Correct 233 ms 91212 KB Output is correct
18 Correct 304 ms 95524 KB Output is correct
19 Correct 185 ms 88952 KB Output is correct
20 Correct 268 ms 93048 KB Output is correct
21 Correct 230 ms 88840 KB Output is correct
22 Correct 283 ms 91160 KB Output is correct
23 Correct 317 ms 92556 KB Output is correct
24 Correct 355 ms 93688 KB Output is correct
25 Correct 389 ms 96348 KB Output is correct