oj.uz

Submission #1010989

# Submission time Handle Problem Language Result Execution time Memory
1010989 2024-06-29T16:24:25 Z bornag Round words (IZhO13_rowords) C++14
20 / 100
 61 ms 126132 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 4007;

int dp[maxn][maxn], ty[maxn][maxn];
int n, m;

void dplcs(string s, string t){
	memset(dp, 0, sizeof dp);
	memset(ty, 0, sizeof ty);
	t += t;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= 2*m; j++){
			dp[i][j] = dp[i-1][j];
			
			if(s[i-1] == t[j-1] and dp[i-1][j-1]+1 > dp[i][j]) dp[i][j] = dp[i-1][j-1]+1, ty[i][j] = 1;
			
			if(dp[i][j-1] > dp[i][j]) dp[i][j] = dp[i][j-1], ty[i][j] = 2;
		}
	}
}

int lcs(int a, int b){
	int ret = 0;
	
	while(a){
		if(ty[a][b] == 1){
			ret++;
			a--;
			b--;
		} else if(ty[a][b] == 2) b--;
		else a--;
	}
	
	return ret;
}

void res(int b){
	int a = 0;
	
	while(b < 2 * m){
		if(ty[a][b+1] == 2){
			ty[a][b+1] = 0;
			b++;
		} else {
			if(a == n) break;
			a++;
			if(ty[a][b+1] == 1){
				ty[a][b+1] = 0;
				b++;
			}
		}
	}
}

int solve(string s, string t){
	dplcs(s, t);
	
	int ret = 0;
	for(int j = 0; j < m; j++){
		ret = max(ret, lcs(n, m+j));
		//res(j);
	}
	
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	string s, t; cin >> s >> t;
	n = s.size(); m = t.size();
	int sol = solve(s, t);
	reverse(t.begin(), t.end());
	sol = max(sol, solve(s, t));
	
	cout << sol << '\n';
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 125876 KB Output is correct
2 Correct 38 ms 126040 KB Output is correct
3 Correct 42 ms 125860 KB Output is correct
4 Correct 40 ms 126036 KB Output is correct
5 Incorrect 40 ms 126036 KB Output isn't correct
6 Incorrect 49 ms 125908 KB Output isn't correct
7 Correct 52 ms 126044 KB Output is correct
8 Incorrect 58 ms 126036 KB Output isn't correct
9 Incorrect 58 ms 125940 KB Output isn't correct
10 Incorrect 53 ms 126036 KB Output isn't correct
11 Incorrect 54 ms 125888 KB Output isn't correct
12 Incorrect 49 ms 126132 KB Output isn't correct
13 Incorrect 58 ms 126040 KB Output isn't correct
14 Incorrect 54 ms 126032 KB Output isn't correct
15 Incorrect 56 ms 126036 KB Output isn't correct
16 Incorrect 61 ms 125940 KB Output isn't correct
17 Incorrect 50 ms 126028 KB Output isn't correct
18 Incorrect 58 ms 126036 KB Output isn't correct
19 Incorrect 58 ms 126036 KB Output isn't correct
20 Incorrect 60 ms 126036 KB Output isn't correct
21 Incorrect 45 ms 126036 KB Output isn't correct
22 Incorrect 47 ms 125940 KB Output isn't correct
23 Incorrect 47 ms 125880 KB Output isn't correct
24 Incorrect 50 ms 126036 KB Output isn't correct
25 Incorrect 53 ms 126032 KB Output isn't correct