Submission #395929

#	Time	Username	Problem	Language	Result	Execution time	Memory
395929		ArshiaDadras	Round words (IZhO13_rowords)	C++14	28 / 100	33 ms	31924 KiB

rowords

/* In the name of Allah */
// Those were the days, my friend...
#include<bits/stdc++.h>
using namespace std;

string s, t;
const int N = 2e3 + 5;
int n, m, dp[N][2 * N], par[N][2 * N];

bool smax(int &a, int b) {
	return a < b? a = b, true: false;
}

int calc(int i, int j, int st) {
	int lcs = 0;
	while (i && j > st)
		if (par[i][j] & 1) {
			i--, j--;
			lcs++;
		}
		else
			par[i][j]? j--: i--;
	return lcs;
}

void read_input() {
	cin >> s >> t;
	n = s.size();
	m = t.size();
}

void solve() {
	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] && smax(dp[i][j], dp[i - 1][j - 1] + 1))
				par[i][j] = 1;
			if (smax(dp[i][j], dp[i][j - 1]))
				par[i][j] = 2;
		}
}

void write_output() {
	int answer = 0;
	for (int i = 0; i < m; i++)
		answer = max(answer, calc(n, m + i, i));
	cout << answer;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}

• Subtask 1: 28 / 100