oj.uz

Submission #17518

# Submission time Handle Problem Language Result Execution time Memory
17518 2015-12-25T11:31:15 Z gs14004 Round words (IZhO13_rowords) C++14
72 / 100
 309 ms 63352 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 = 1;
	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){
	memset(dp,0,sizeof(dp));
	memset(nxt,0,sizeof(nxt));
	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
72.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 63096 KB Output is correct
2 Incorrect 66 ms 63224 KB Output isn't correct
3 Correct 66 ms 63100 KB Output is correct
4 Correct 80 ms 63220 KB Output is correct
5 Incorrect 75 ms 63324 KB Output isn't correct
6 Correct 85 ms 63224 KB Output is correct
7 Correct 94 ms 63224 KB Output is correct
8 Correct 173 ms 63228 KB Output is correct
9 Correct 163 ms 63260 KB Output is correct
10 Correct 149 ms 63352 KB Output is correct
11 Correct 180 ms 63196 KB Output is correct
12 Correct 155 ms 63228 KB Output is correct
13 Correct 193 ms 63224 KB Output is correct
14 Incorrect 172 ms 63224 KB Output isn't correct
15 Correct 212 ms 63224 KB Output is correct
16 Incorrect 181 ms 63224 KB Output isn't correct
17 Correct 180 ms 63352 KB Output is correct
18 Incorrect 230 ms 63224 KB Output isn't correct
19 Incorrect 151 ms 63300 KB Output isn't correct
20 Correct 201 ms 63196 KB Output is correct
21 Correct 190 ms 63196 KB Output is correct
22 Correct 221 ms 63224 KB Output is correct
23 Correct 227 ms 63268 KB Output is correct
24 Incorrect 257 ms 63224 KB Output isn't correct
25 Correct 309 ms 63284 KB Output is correct