답안 #508816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508816	2022-01-13T20:41:33 Z	dutch	원형 문자열 (IZhO13_rowords)	C++17	72 / 100	838 ms	46528 KB

rowords

#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++) {
			int w = d[i][j];
			if(d[i+1][j+1] > w && S[i] == T[j])
				d[i+1][j+1] = w, p[i+1][j+1] = 3;
			++w;
			if(d[i+1][j] > w)
				d[i+1][j] = w, p[i+1][j] = 1;
			if(d[i][j+1] > w)
				d[i][j+1] = w, 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 + M - d[i][j]) / 2 - 1);
 
	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 += '_';
	S += '.';
	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

72.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	460 KB	Output is correct
2	Incorrect	0 ms	460 KB	Output isn't correct
3	Correct	0 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	98 ms	17936 KB	Output is correct
7	Correct	573 ms	31740 KB	Output is correct
8	Correct	458 ms	31736 KB	Output is correct
9	Correct	493 ms	31808 KB	Output is correct
10	Correct	485 ms	31736 KB	Output is correct
11	Correct	534 ms	34888 KB	Output is correct
12	Correct	581 ms	38084 KB	Output is correct
13	Correct	706 ms	38024 KB	Output is correct
14	Incorrect	617 ms	36080 KB	Output isn't correct
15	Correct	744 ms	39160 KB	Output is correct
16	Incorrect	638 ms	34300 KB	Output isn't correct
17	Correct	555 ms	36584 KB	Output is correct
18	Incorrect	838 ms	44840 KB	Output isn't correct
19	Incorrect	448 ms	31652 KB	Output isn't correct
20	Correct	766 ms	40064 KB	Output is correct
21	Correct	330 ms	31684 KB	Output is correct
22	Correct	450 ms	36268 KB	Output is correct
23	Correct	579 ms	39096 KB	Output is correct
24	Incorrect	654 ms	41240 KB	Output isn't correct
25	Correct	777 ms	46528 KB	Output is correct