oj.uz

Submission #395943

# Submission time Handle Problem Language Result Execution time Memory
395943 2021-04-29T08:51:43 Z ArshiaDadras Round words (IZhO13_rowords) C++14
36 / 100
 51 ms 32716 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++) {
			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 - 1][j]))
				par[i][j] = 0;
			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 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Incorrect 8 ms 9952 KB Output isn't correct
7 Correct 15 ms 388 KB Output is correct
8 Incorrect 46 ms 23884 KB Output isn't correct
9 Incorrect 41 ms 24012 KB Output isn't correct
10 Incorrect 33 ms 23964 KB Output isn't correct
11 Incorrect 36 ms 26312 KB Output isn't correct
12 Correct 39 ms 30008 KB Output is correct
13 Correct 48 ms 30052 KB Output is correct
14 Incorrect 40 ms 27416 KB Output isn't correct
15 Incorrect 45 ms 31656 KB Output isn't correct
16 Incorrect 51 ms 26248 KB Output isn't correct
17 Incorrect 32 ms 24932 KB Output isn't correct
18 Incorrect 45 ms 32716 KB Output isn't correct
19 Incorrect 34 ms 24000 KB Output isn't correct
20 Incorrect 50 ms 29296 KB Output isn't correct
21 Correct 17 ms 18020 KB Output is correct
22 Incorrect 24 ms 21868 KB Output isn't correct
23 Incorrect 27 ms 24684 KB Output isn't correct
24 Incorrect 33 ms 25948 KB Output isn't correct
25 Incorrect 39 ms 30412 KB Output isn't correct