oj.uz

Submission #508825

# Submission time Handle Problem Language Result Execution time Memory
508825 2022-01-13T21:07:36 Z dutch Round words (IZhO13_rowords) C++17
100 / 100
 931 ms 46492 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int Z = 2002, 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, j = M-1;
 
	assert(lo[M-1] <= i && i <= hi[M-1]);
	assert((N + M - d[i][j]) & 1);
	ans = max(ans, (N + M - d[i][j] - 1) / 2);
 
	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;
	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;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 984 KB Output is correct
5 Correct 1 ms 948 KB Output is correct
6 Correct 119 ms 17916 KB Output is correct
7 Correct 610 ms 31780 KB Output is correct
8 Correct 622 ms 31708 KB Output is correct
9 Correct 572 ms 31664 KB Output is correct
10 Correct 543 ms 31708 KB Output is correct
11 Correct 654 ms 34848 KB Output is correct
12 Correct 686 ms 38040 KB Output is correct
13 Correct 811 ms 38056 KB Output is correct
14 Correct 681 ms 36104 KB Output is correct
15 Correct 860 ms 39184 KB Output is correct
16 Correct 704 ms 34164 KB Output is correct
17 Correct 664 ms 36560 KB Output is correct
18 Correct 931 ms 44840 KB Output is correct
19 Correct 545 ms 31704 KB Output is correct
20 Correct 884 ms 40032 KB Output is correct
21 Correct 390 ms 31584 KB Output is correct
22 Correct 539 ms 36292 KB Output is correct
23 Correct 652 ms 39068 KB Output is correct
24 Correct 754 ms 41216 KB Output is correct
25 Correct 856 ms 46492 KB Output is correct