oj.uz

Submission #508803

# Submission time Handle Problem Language Result Execution time Memory
508803 2022-01-13T19:39:31 Z dutch Round words (IZhO13_rowords) C++17
80 / 100
 1985 ms 46456 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] || x < lo[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
80.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 2 ms 972 KB Output is correct
5 Incorrect 2 ms 972 KB Output isn't correct
6 Correct 192 ms 17848 KB Output is correct
7 Correct 1010 ms 31692 KB Output is correct
8 Correct 1228 ms 31712 KB Output is correct
9 Correct 1372 ms 31748 KB Output is correct
10 Correct 1431 ms 31816 KB Output is correct
11 Correct 1573 ms 34836 KB Output is correct
12 Correct 1643 ms 38072 KB Output is correct
13 Correct 1906 ms 38068 KB Output is correct
14 Incorrect 1683 ms 36312 KB Output isn't correct
15 Correct 1985 ms 39220 KB Output is correct
16 Correct 1552 ms 34164 KB Output is correct
17 Correct 1309 ms 36328 KB Output is correct
18 Incorrect 1982 ms 44732 KB Output isn't correct
19 Incorrect 1330 ms 31712 KB Output isn't correct
20 Correct 1733 ms 39980 KB Output is correct
21 Correct 589 ms 31432 KB Output is correct
22 Correct 886 ms 35972 KB Output is correct
23 Correct 1151 ms 38604 KB Output is correct
24 Incorrect 1251 ms 40824 KB Output isn't correct
25 Correct 1637 ms 46456 KB Output is correct