oj.uz

답안 #395929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395929 2021-04-29T08:18:28 Z ArshiaDadras 원형 문자열 (IZhO13_rowords) C++14
28 / 100
 33 ms 31924 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(int i, int j, int st) {
	int lcs = 0;
	while (i && j > st)
		if (par[i][j] & 1) {
			i--, j--;
			lcs++;
		}
		else
			par[i][j]? j--: i--;
	return lcs;
}

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

void solve() {
	t += t;
	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] = 1;
			if (smax(dp[i][j], dp[i][j - 1]))
				par[i][j] = 2;
		}
}

void write_output() {
	int answer = 0;
	for (int i = 0; i < m; i++)
		answer = max(answer, calc(n, m + i, i));
	cout << answer;
}

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

Subtask #1
28.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't 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 2 ms 588 KB Output is correct
6 Correct 5 ms 8396 KB Output is correct
7 Correct 13 ms 12112 KB Output is correct
8 Incorrect 24 ms 22860 KB Output isn't correct
9 Incorrect 24 ms 23456 KB Output isn't correct
10 Incorrect 21 ms 23628 KB Output isn't correct
11 Incorrect 21 ms 25852 KB Output isn't correct
12 Correct 22 ms 27292 KB Output is correct
13 Incorrect 33 ms 29276 KB Output isn't correct
14 Incorrect 24 ms 26796 KB Output isn't correct
15 Incorrect 27 ms 31052 KB Output isn't correct
16 Incorrect 27 ms 25292 KB Output isn't correct
17 Incorrect 18 ms 24036 KB Output isn't correct
18 Incorrect 26 ms 31924 KB Output isn't correct
19 Incorrect 20 ms 23460 KB Output isn't correct
20 Incorrect 28 ms 28364 KB Output isn't correct
21 Incorrect 11 ms 16480 KB Output isn't correct
22 Incorrect 15 ms 20484 KB Output isn't correct
23 Incorrect 16 ms 23372 KB Output isn't correct
24 Incorrect 18 ms 24680 KB Output isn't correct
25 Incorrect 21 ms 29196 KB Output isn't correct