oj.uz

Submission #508813

# Submission time Handle Problem Language Result Execution time Memory
508813 2022-01-13T20:21:52 Z dutch Round words (IZhO13_rowords) C++17
80 / 100
 846 ms 46480 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int Z = 2001, INF = 1e8;
 
string S, T;
int N, M, ans, d[Z*2][Z], p[Z*2][Z];
 
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;

	d[rt][0] = 0;

	for(int j = 0; j < M; j++) {
		for(int i = lo[j]; i <= hi[j]; i++) {
			if(d[i+1][j+1] > d[i][j] && S[i] == T[j])
				d[i+1][j+1] = d[i][j], p[i+1][j+1] = 3;
			if(d[i+1][j] > d[i][j] + 1)
				d[i+1][j] = d[i][j] + 1, p[i+1][j] = 1;
			if(d[i][j+1] > d[i][j] + 1)
				d[i][j+1] = d[i][j] + 1, p[i][j+1] = 2;
		}
	}
 
	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);
	S += S;
 
	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
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Incorrect 1 ms 972 KB Output isn't correct
6 Correct 106 ms 17904 KB Output is correct
7 Correct 526 ms 31812 KB Output is correct
8 Correct 489 ms 31700 KB Output is correct
9 Correct 479 ms 31696 KB Output is correct
10 Correct 445 ms 31796 KB Output is correct
11 Correct 602 ms 34840 KB Output is correct
12 Correct 619 ms 37984 KB Output is correct
13 Correct 759 ms 37980 KB Output is correct
14 Incorrect 602 ms 36088 KB Output isn't correct
15 Correct 753 ms 39112 KB Output is correct
16 Correct 625 ms 34152 KB Output is correct
17 Correct 546 ms 36520 KB Output is correct
18 Incorrect 846 ms 44828 KB Output isn't correct
19 Incorrect 471 ms 31692 KB Output isn't correct
20 Correct 777 ms 40092 KB Output is correct
21 Correct 340 ms 31540 KB Output is correct
22 Correct 491 ms 36220 KB Output is correct
23 Correct 580 ms 39036 KB Output is correct
24 Incorrect 644 ms 41160 KB Output isn't correct
25 Correct 834 ms 46480 KB Output is correct