Submission #508832

#	Time	Username	Problem	Language	Result	Execution time	Memory
508832		dutch	Round words (IZhO13_rowords)	C++17	100 / 100	934 ms	46528 KiB

rowords

#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 / 100