Submission #13624

#	Time	Username	Problem	Language	Result	Execution time	Memory
13624		tncks0121	Round words (IZhO13_rowords)	C++14	100 / 100	337 ms	56056 KiB

rowords

#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) 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 (stderr)

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 / 100