Submission #1010986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010986		bornag	Round words (IZhO13_rowords)	C++14	100 / 100	95 ms	126288 KiB

rowords

#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: 100 / 100