oj.uz

Submission #17517

# Submission time Handle Problem Language Result Execution time Memory
17517 2015-12-25T11:27:28 Z gs14004 Round words (IZhO13_rowords) C++14
52 / 100
 160 ms 46456 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 dx[3] = {-1, -1, 0}, dy[3] = {0, -1, -1};
int n, m;

void solve(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 main(){
	cin >> s1 >> s2;
	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++){
		solve(i);
		ret = max(ret, track(n-1+i, m, i));
	}
	cout << ret;
}

Subtask #1
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Incorrect 3 ms 1016 KB Output isn't correct
6 Correct 27 ms 17912 KB Output is correct
7 Correct 42 ms 31736 KB Output is correct
8 Incorrect 77 ms 31740 KB Output isn't correct
9 Correct 77 ms 31796 KB Output is correct
10 Correct 70 ms 31736 KB Output is correct
11 Correct 77 ms 34936 KB Output is correct
12 Correct 85 ms 38052 KB Output is correct
13 Correct 108 ms 38028 KB Output is correct
14 Incorrect 88 ms 36156 KB Output isn't correct
15 Correct 93 ms 39288 KB Output is correct
16 Incorrect 89 ms 34236 KB Output isn't correct
17 Incorrect 97 ms 36472 KB Output isn't correct
18 Incorrect 127 ms 44792 KB Output isn't correct
19 Incorrect 68 ms 31736 KB Output isn't correct
20 Incorrect 105 ms 39928 KB Output isn't correct
21 Correct 85 ms 31736 KB Output is correct
22 Correct 110 ms 36216 KB Output is correct
23 Correct 117 ms 39032 KB Output is correct
24 Incorrect 133 ms 41208 KB Output isn't correct
25 Incorrect 160 ms 46456 KB Output isn't correct