oj.uz

Submission #395936

# Submission time Handle Problem Language Result Execution time Memory
395936 2021-04-29T08:47:10 Z ArshiaDadras Round words (IZhO13_rowords) C++14
36 / 100
 42 ms 32220 KB 
/* 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_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++) {
			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] = 2;
			if (smax(dp[i][j], dp[i][j - 1]))
				par[i][j] = 1;
		}
}

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();
	t += t;
}

void solve() {
	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
36.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 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 6 ms 8780 KB Output is correct
7 Correct 17 ms 12108 KB Output is correct
8 Incorrect 37 ms 22956 KB Output isn't correct
9 Incorrect 34 ms 23492 KB Output isn't correct
10 Incorrect 28 ms 23628 KB Output isn't correct
11 Incorrect 29 ms 25976 KB Output isn't correct
12 Correct 28 ms 27248 KB Output is correct
13 Incorrect 40 ms 29528 KB Output isn't correct
14 Incorrect 32 ms 27004 KB Output isn't correct
15 Incorrect 36 ms 31220 KB Output isn't correct
16 Incorrect 42 ms 25292 KB Output isn't correct
17 Incorrect 23 ms 24268 KB Output isn't correct
18 Incorrect 34 ms 32220 KB Output isn't correct
19 Incorrect 27 ms 23620 KB Output isn't correct
20 Incorrect 41 ms 28388 KB Output isn't correct
21 Correct 13 ms 16972 KB Output is correct
22 Incorrect 18 ms 20756 KB Output isn't correct
23 Incorrect 20 ms 23756 KB Output isn't correct
24 Incorrect 22 ms 25068 KB Output isn't correct
25 Incorrect 28 ms 29516 KB Output isn't correct