답안 #17519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17519	2015-12-25T11:44:36 Z	gs14004	원형 문자열 (IZhO13_rowords)	C++14	84 / 100	290 ms	46552 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(x >= e && y >= 1){
		if(nxt[x][y] == 2) ret += (s1[x] == s2[y]), x--, y--;
		if(nxt[x][y] == 1) y--;
		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));
	}
	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	36 ms	18000 KB	Output is correct
7	Correct	56 ms	31736 KB	Output is correct
8	Correct	133 ms	31736 KB	Output is correct
9	Correct	130 ms	31736 KB	Output is correct
10	Correct	118 ms	31764 KB	Output is correct
11	Correct	130 ms	34936 KB	Output is correct
12	Correct	140 ms	38008 KB	Output is correct
13	Correct	178 ms	38008 KB	Output is correct
14	Incorrect	138 ms	36160 KB	Output isn't correct
15	Correct	154 ms	39160 KB	Output is correct
16	Incorrect	150 ms	34168 KB	Output isn't correct
17	Correct	146 ms	36544 KB	Output is correct
18	Correct	202 ms	44892 KB	Output is correct
19	Incorrect	108 ms	31736 KB	Output isn't correct
20	Correct	180 ms	40060 KB	Output is correct
21	Correct	153 ms	31632 KB	Output is correct
22	Correct	189 ms	36344 KB	Output is correct
23	Correct	200 ms	39148 KB	Output is correct
24	Incorrect	233 ms	41208 KB	Output isn't correct
25	Correct	290 ms	46552 KB	Output is correct