oj.uz

Submission #1010980

# Submission time Handle Problem Language Result Execution time Memory
1010980 2024-06-29T16:13:27 Z bornag Round words (IZhO13_rowords) C++14
48 / 100
 49 ms 34132 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){
	t = 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 i = 0; i < m; i++){
		ret = max(ret, lcs(n, m+i));
		res(i);
	}
	
	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
48.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 5 ms 13176 KB Output is correct
7 Correct 15 ms 13696 KB Output is correct
8 Correct 41 ms 24664 KB Output is correct
9 Incorrect 39 ms 25172 KB Output isn't correct
10 Incorrect 32 ms 25432 KB Output isn't correct
11 Incorrect 30 ms 27484 KB Output isn't correct
12 Correct 24 ms 28764 KB Output is correct
13 Incorrect 47 ms 30808 KB Output isn't correct
14 Incorrect 34 ms 28504 KB Output isn't correct
15 Incorrect 38 ms 32592 KB Output isn't correct
16 Incorrect 49 ms 26868 KB Output isn't correct
17 Incorrect 25 ms 27224 KB Output isn't correct
18 Incorrect 37 ms 34132 KB Output isn't correct
19 Incorrect 28 ms 25180 KB Output isn't correct
20 Incorrect 43 ms 30460 KB Output isn't correct
21 Correct 10 ms 21080 KB Output is correct
22 Correct 18 ms 24920 KB Output is correct
23 Correct 20 ms 27228 KB Output is correct
24 Incorrect 26 ms 28748 KB Output isn't correct
25 Incorrect 26 ms 32856 KB Output isn't correct