답안 #395934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395934	2021-04-29T08:37:11 Z	ArshiaDadras	원형 문자열 (IZhO13_rowords)	C++14	32 / 100	58 ms	32712 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) % 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

#	결과	실행 시간	메모리	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