oj.uz

Submission #17520

# Submission time Handle Problem Language Result Execution time Memory
17520 2015-12-25T11:54:09 Z gs14004 Round words (IZhO13_rowords) C++14
84 / 100
 278 ms 46712 KB 
#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

# Verdict Execution time Memory 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