답안 #250917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250917	2020-07-19T12:18:30 Z	srvlt	원형 문자열 (IZhO13_rowords)	C++14	28 / 100	189 ms	504 KB

rowords

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 2003, inf = 1e9;

struct T {
	int len, d1, d2;
	void clean() {
		len = 0, d1 = 0, d2 = 0;
	}
	void upd(const T & t) {
		if (t.len + 1 > len || (t.len + 1 == len && (t.len == 0 || t.d1 < d1 || t.d2 + 1 < d2))) {
			len = t.len + 1;
			if (t.len > 0) {
				d1 = t.d1;
				d2 = t.d2 + 1;
			}	else {
				d1 = 0, d2 = 0;
			}
		}
	}
	void mx(const T & t) {
		if (t.len > len || (t.len == len && (t.len == 0 || t.d1 < d1 || t.d2 + 1 < d2))) {
			len = t.len;
			if (t.len > 0) {
				d1 = t.d1;
				d2 = t.d2 + 1;
			}	else {
				d1 = 0, d2 = 0;
			}
		}
	}
};
T dp[n0];

int LCS(const string & a, const string & b) {
	int n = SZ(a), m = SZ(b);
	for (int j = 1; j <= m; j++)
		dp[j].clean();
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 1; j--) {
			if (dp[j].len > 0) dp[j].d1++;
			if (a[i - 1] == b[j - 1])
				dp[j].upd(dp[j - 1]);
		}
		for (int j = 1; j <= m; j++)
			dp[j].mx(dp[j - 1]);
		for (int j = 1; j <= m; j++)
			if (dp[j].d1 >= n / 2 || dp[j].d2 >= m / 2)
				dp[j].clean();
	}
	int res = 0;
	for (int j = 1; j <= m; j++) {
		res = max(res, dp[j].len);
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	string a, b, A, B;
	cin >> a >> b;
	int res = 0;
	for (int i = 0; i < 4; i++) {
		A = a, B = b;
		if (i & 1) reverse(all(A));
		if (i & 2) reverse(all(B));
		A += A, B += B;
		res = max(res, LCS(A, B));
	}
	cout << res;
}

Subtask #1

28.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Incorrect	1 ms	384 KB	Output isn't correct
6	Correct	10 ms	384 KB	Output is correct
7	Correct	76 ms	384 KB	Output is correct
8	Incorrect	145 ms	384 KB	Output isn't correct
9	Incorrect	145 ms	504 KB	Output isn't correct
10	Incorrect	113 ms	504 KB	Output isn't correct
11	Incorrect	114 ms	384 KB	Output isn't correct
12	Correct	112 ms	384 KB	Output is correct
13	Incorrect	173 ms	384 KB	Output isn't correct
14	Incorrect	129 ms	504 KB	Output isn't correct
15	Incorrect	144 ms	384 KB	Output isn't correct
16	Incorrect	189 ms	504 KB	Output isn't correct
17	Incorrect	90 ms	384 KB	Output isn't correct
18	Incorrect	137 ms	504 KB	Output isn't correct
19	Incorrect	106 ms	384 KB	Output isn't correct
20	Incorrect	165 ms	384 KB	Output isn't correct
21	Incorrect	24 ms	384 KB	Output isn't correct
22	Incorrect	49 ms	384 KB	Output isn't correct
23	Incorrect	65 ms	384 KB	Output isn't correct
24	Incorrect	69 ms	384 KB	Output isn't correct
25	Incorrect	93 ms	384 KB	Output isn't correct