oj.uz

Submission #508792

# Submission time Handle Problem Language Result Execution time Memory
508792 2022-01-13T19:05:32 Z dutch Round words (IZhO13_rowords) C++17
36 / 100
 2000 ms 46460 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];

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

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

	int rt = (loR + hiR) / 2;
	deque<array<int, 2>> q;
	q.push_back({rt, d[rt][0] = 0});

	while(!empty(q)) {
		auto [i, j] = q.front();
		q.pop_front();
		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;
			if(w) q.push_back({x, y});
			else q.push_front({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
36.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Incorrect 2 ms 972 KB Output isn't correct
6 Correct 317 ms 17856 KB Output is correct
7 Correct 977 ms 31816 KB Output is correct
8 Correct 1736 ms 31940 KB Output is correct
9 Execution timed out 2049 ms 31668 KB Time limit exceeded
10 Execution timed out 2087 ms 31828 KB Time limit exceeded
11 Execution timed out 2078 ms 34844 KB Time limit exceeded
12 Correct 1686 ms 38000 KB Output is correct
13 Execution timed out 2076 ms 38044 KB Time limit exceeded
14 Execution timed out 2041 ms 36320 KB Time limit exceeded
15 Execution timed out 2055 ms 39112 KB Time limit exceeded
16 Execution timed out 2080 ms 34184 KB Time limit exceeded
17 Execution timed out 2055 ms 36520 KB Time limit exceeded
18 Execution timed out 2053 ms 44772 KB Time limit exceeded
19 Execution timed out 2080 ms 31784 KB Time limit exceeded
20 Execution timed out 2084 ms 39972 KB Time limit exceeded
21 Correct 1154 ms 31432 KB Output is correct
22 Execution timed out 2007 ms 36052 KB Time limit exceeded
23 Execution timed out 2086 ms 38688 KB Time limit exceeded
24 Execution timed out 2080 ms 40772 KB Time limit exceeded
25 Execution timed out 2098 ms 46460 KB Time limit exceeded