oj.uz

Submission #508832

# Submission time Handle Problem Language Result Execution time Memory
508832 2022-01-13T21:20:57 Z dutch Round words (IZhO13_rowords) C++17
100 / 100
 934 ms 46528 KB 
#include <bits/stdc++.h>
using namespace std;
#define D d[i][j]
#define F for(int j = 0; j < M; j++) for(int i = lo[j]; i <= hi[j]; i++) 

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;

	int rt = (loR + hiR) / 2;
 
	F d[i][j] = INF;
	d[rt][0] = 0;
 	
 	F {
 		if(d[i+1][j+1] > D && S[i] == T[j])
				d[i+1][j+1] = D, p[i+1][j+1] = 3;
		for(int k : {1, 0})
			if(d[i+k][j+!k] > D + 1)
				d[i+k][j+!k] = D + 1, p[i+k][j+!k] = !k+1;
	}
 
	int mMin[M], mMax[M] = {};
	fill(mMin, mMin+M, N+N);
 
	int i = rt+N, j = M-1;
	ans = max(ans, (N+M-D-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 1 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 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 122 ms 17820 KB Output is correct
7 Correct 571 ms 31772 KB Output is correct
8 Correct 543 ms 31604 KB Output is correct
9 Correct 488 ms 31696 KB Output is correct
10 Correct 454 ms 31796 KB Output is correct
11 Correct 618 ms 34884 KB Output is correct
12 Correct 686 ms 37984 KB Output is correct
13 Correct 800 ms 37980 KB Output is correct
14 Correct 702 ms 36092 KB Output is correct
15 Correct 853 ms 39116 KB Output is correct
16 Correct 723 ms 34268 KB Output is correct
17 Correct 628 ms 36548 KB Output is correct
18 Correct 934 ms 44876 KB Output is correct
19 Correct 507 ms 31712 KB Output is correct
20 Correct 823 ms 40044 KB Output is correct
21 Correct 369 ms 31592 KB Output is correct
22 Correct 551 ms 36316 KB Output is correct
23 Correct 625 ms 38980 KB Output is correct
24 Correct 693 ms 41208 KB Output is correct
25 Correct 869 ms 46528 KB Output is correct