Submission #395930

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
395930	2021-04-29T08:32:13 Z	ArshiaDadras	Round words (IZhO13_rowords)	C++14	32 / 100	46 ms	32716 KB

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];

int calc_lcs(int j) {
	int lcs = 0;
	for (int i = n, st = j - m; i && j > st; )
		if (par[i][j] & 2) {
			i--, j--;
			lcs++;
		}
		else
			par[i][j]? j--: i--;
	return lcs;
}

void build_dp() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 2 * m; j++)
			if (s[i - 1] == t[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				par[i][j] = 2;
			}
			else {
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
				par[i][j] = dp[i][j] > dp[i - 1][j];
			}
}

int calc_round_lcs() {
	int answer = 0;
	for (int i = 0; i < m; i++)
		answer = max(answer, calc_lcs(m + i));
	return answer;
}

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

void solve() {
	t += t;
	int answer = 0;
	for (int i = 0; i < 2; i++) {
		build_dp();
		reverse(t.begin(), t.end());
		answer = max(answer, calc_round_lcs());
	}
	cout << answer;
}

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

Subtask #1

32.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	1 ms	716 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	7 ms	9944 KB	Output is correct
7	Correct	37 ms	24012 KB	Output is correct
8	Incorrect	30 ms	24140 KB	Output isn't correct
9	Incorrect	31 ms	24012 KB	Output isn't correct
10	Incorrect	34 ms	23892 KB	Output isn't correct
11	Incorrect	38 ms	26388 KB	Output isn't correct
12	Correct	28 ms	30068 KB	Output is correct
13	Incorrect	40 ms	30028 KB	Output isn't correct
14	Incorrect	38 ms	27340 KB	Output isn't correct
15	Incorrect	46 ms	31672 KB	Output isn't correct
16	Incorrect	35 ms	26248 KB	Output isn't correct
17	Incorrect	29 ms	24920 KB	Output isn't correct
18	Incorrect	44 ms	32716 KB	Output isn't correct
19	Incorrect	34 ms	23892 KB	Output isn't correct
20	Incorrect	36 ms	29312 KB	Output isn't correct
21	Incorrect	15 ms	17956 KB	Output isn't correct
22	Incorrect	25 ms	21872 KB	Output isn't correct
23	Incorrect	26 ms	24612 KB	Output isn't correct
24	Incorrect	33 ms	25924 KB	Output isn't correct
25	Incorrect	35 ms	30504 KB	Output isn't correct