oj.uz

Submission #508795

# Submission time Handle Problem Language Result Execution time Memory
508795 2022-01-13T19:15:50 Z dutch Round words (IZhO13_rowords) C++17
52 / 100
 2000 ms 59676 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 2000, INF = 1e8;

string S, T;
int N, M, ans, d[Z*2][Z], p[Z*2][Z];
array<int, 2> _q[(int)1e7], *_l, *_r;

#define init() _r = _l = _q + (int)5e6

void dfs(int loR, int hiR, int *lo, int *hi) {
	if(loR > hiR) return;

	for(int j = 0; j < M; j++)
		for(int i = lo[j]; i <= hi[j]; i++) 
			d[i][j] = INF;

	int rt = (loR + hiR) / 2;

	init();
	(*_r++) = {rt, d[rt][0] = 0};

	while(_l != _r) {
		auto [i, j] = (*_l++);
		for(int di : {0, 1}) for(int dj : {0, 1}) {
			int x = i + di, y = j + dj, w = di ^ dj;
			if(y == M || x > hi[y] || d[x][y] <= d[i][j] + w) continue;
			if(di && dj && S[i % N] != T[j]) continue;

			d[x][y] = d[i][j] + w;
			p[x][y] = di + 2 * dj;

			(w ? *_r++ : *--_l) = {x, y};
		}
	}

	int mMin[M], mMax[M] = {};
	fill(mMin, mMin+M, N+N);

	int i = rt+N-1, j = M-1;

	assert(lo[M-1] <= i && i <= hi[M-1]);
	ans = max(ans, N-1 + M-1 - d[i][j] + 2 * (S[i%N] == T[j]));

	while(1) {
		mMin[j] = min(mMin[j], i);
		mMax[j] = max(mMax[j], i);
		if(i == rt && !j) break;
		int k = p[i][j];
		if(k & 1) --i;
		if(k & 2) --j;
	}

	dfs(loR, rt - 1, lo, mMax);
	dfs(rt + 1, hiR, mMin, hi);
}

int main() {
	cin >> S >> T;
	N = size(S);
	M = size(T);

	for(int _ : {0, 1}) {
		if(_) reverse(begin(S), end(S));
		int lo[M] = {}, hi[M];
		fill(hi, hi + M, 2 * N - 1);

		dfs(0, N-1, lo, hi);
	}
	cout << ans / 2;
}

Subtask #1
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Incorrect 3 ms 972 KB Output isn't correct
6 Correct 212 ms 19028 KB Output is correct
7 Correct 709 ms 43436 KB Output is correct
8 Correct 1308 ms 42660 KB Output is correct
9 Correct 1881 ms 42744 KB Output is correct
10 Execution timed out 2037 ms 43068 KB Time limit exceeded
11 Execution timed out 2091 ms 47440 KB Time limit exceeded
12 Correct 1258 ms 53048 KB Output is correct
13 Execution timed out 2101 ms 52236 KB Time limit exceeded
14 Execution timed out 2082 ms 49136 KB Time limit exceeded
15 Execution timed out 2102 ms 54724 KB Time limit exceeded
16 Correct 1901 ms 46344 KB Output is correct
17 Execution timed out 2081 ms 46160 KB Time limit exceeded
18 Execution timed out 2077 ms 59676 KB Time limit exceeded
19 Execution timed out 2083 ms 43064 KB Time limit exceeded
20 Execution timed out 2087 ms 53176 KB Time limit exceeded
21 Correct 829 ms 34344 KB Output is correct
22 Correct 1431 ms 41760 KB Output is correct
23 Correct 1858 ms 46412 KB Output is correct
24 Execution timed out 2028 ms 49092 KB Time limit exceeded
25 Execution timed out 2080 ms 56840 KB Time limit exceeded