oj.uz

Submission #395934

# Submission time Handle Problem Language Result Execution time Memory
395934 2021-04-29T08:37:11 Z ArshiaDadras Round words (IZhO13_rowords) C++14
32 / 100
 58 ms 32712 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];

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) % m]) {
				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() {
	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 460 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 8 ms 9932 KB Output is correct
7 Correct 42 ms 23884 KB Output is correct
8 Incorrect 48 ms 23884 KB Output isn't correct
9 Incorrect 49 ms 23884 KB Output isn't correct
10 Incorrect 43 ms 23964 KB Output isn't correct
11 Incorrect 47 ms 26368 KB Output isn't correct
12 Correct 48 ms 30012 KB Output is correct
13 Incorrect 56 ms 30020 KB Output isn't correct
14 Incorrect 48 ms 27332 KB Output isn't correct
15 Incorrect 58 ms 31664 KB Output isn't correct
16 Incorrect 55 ms 26168 KB Output isn't correct
17 Incorrect 37 ms 24936 KB Output isn't correct
18 Incorrect 56 ms 32712 KB Output isn't correct
19 Incorrect 43 ms 23876 KB Output isn't correct
20 Incorrect 54 ms 29252 KB Output isn't correct
21 Incorrect 17 ms 17916 KB Output isn't correct
22 Incorrect 25 ms 21836 KB Output isn't correct
23 Incorrect 32 ms 24676 KB Output isn't correct
24 Incorrect 33 ms 26036 KB Output isn't correct
25 Incorrect 42 ms 30416 KB Output isn't correct