답안 #17520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17520	2015-12-25T11:54:09 Z	gs14004	원형 문자열 (IZhO13_rowords)	C++14	84 / 100	278 ms	46712 KB

rowords

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <complex>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
typedef complex<double> pnt;

string s1, s2;

int dp[4005][2005];
int nxt[4005][2005];
int n, m;

void reroot(int px){
	int py = 2;
	while(py <= m && nxt[px][py] != 2) py++;
	nxt[px][py] = 1;
	while(px < 2 * n && py < m){
		if(nxt[px+1][py] == 3){
			px++;
			nxt[px][py] = 1;
		}
		else if(nxt[px+1][py+1] == 2){
			px++;
			py++;
			nxt[px][py] = 1;
		}
		else py++;
	}
	while(px < 2 * n && nxt[px+1][py] == 3){
		px++;
		nxt[px][py] = 1;
	}
}

int track(int x, int y, int e){
	int ret = 0;
	while(y != 0 && x != e){
		if(nxt[x][y] == 1) y--;
		else if(nxt[x][y] == 2) ret += (s1[x] == s2[y]), x--, y--;
		else if(nxt[x][y] == 3) x--;
	}
	return ret;
}

int solve(string a, string b){
	s1 = a, s2 = b;
	n = s1.size(), m = s2.size();
	s1 = s1 + s1;
	s1 = '#' + s1;
	s2 = '#' + s2;
	for(int i=1; i<=2*n; i++){
		for(int j=1; j<=m; j++){
			dp[i][j] = -1;
			if(dp[i][j] < dp[i][j-1]){
				dp[i][j] = dp[i][j-1];
				nxt[i][j] = 1;
			}
			if(dp[i][j] < dp[i-1][j-1] + (s1[i] == s2[j])){
				dp[i][j] = dp[i-1][j-1] + (s1[i] == s2[j]);
				nxt[i][j] = 2;
			}
			if(dp[i][j] < dp[i-1][j]){
				dp[i][j] = dp[i-1][j];
				nxt[i][j] = 3;
			}
		}
	}
	int ret = dp[n][m];
	for(int i=2; i<=n; i++){
		reroot(i);
		ret = max(ret, track(n-1+i, m, i-1));
	}
	return ret;
}

int main(){
	string a, b;
	cin >> a >> b;
	int ret = solve(a, b);
	reverse(b.begin(), b.end());
	ret = max(ret, solve(a, b));
	cout << ret;
}

Subtask #1

84.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	632 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	1016 KB	Output is correct
6	Correct	35 ms	17912 KB	Output is correct
7	Correct	45 ms	31736 KB	Output is correct
8	Correct	112 ms	31772 KB	Output is correct
9	Correct	116 ms	31736 KB	Output is correct
10	Correct	106 ms	31736 KB	Output is correct
11	Correct	115 ms	34936 KB	Output is correct
12	Correct	84 ms	38008 KB	Output is correct
13	Correct	162 ms	38136 KB	Output is correct
14	Incorrect	135 ms	36088 KB	Output isn't correct
15	Correct	153 ms	39160 KB	Output is correct
16	Incorrect	130 ms	34152 KB	Output isn't correct
17	Correct	144 ms	36476 KB	Output is correct
18	Correct	188 ms	44796 KB	Output is correct
19	Incorrect	102 ms	31864 KB	Output isn't correct
20	Correct	168 ms	40184 KB	Output is correct
21	Correct	143 ms	31608 KB	Output is correct
22	Correct	188 ms	36316 KB	Output is correct
23	Correct	199 ms	39164 KB	Output is correct
24	Incorrect	226 ms	41336 KB	Output isn't correct
25	Correct	278 ms	46712 KB	Output is correct