답안 #250920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250920 2020-07-19T12:21:01 Z srvlt 원형 문자열 (IZhO13_rowords) C++14
28 / 100
179 ms 508 KB
#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))) {
			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))) {
			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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 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 75 ms 384 KB Output is correct
8 Incorrect 173 ms 508 KB Output isn't correct
9 Incorrect 157 ms 384 KB Output isn't correct
10 Incorrect 119 ms 384 KB Output isn't correct
11 Incorrect 123 ms 384 KB Output isn't correct
12 Correct 124 ms 416 KB Output is correct
13 Incorrect 179 ms 384 KB Output isn't correct
14 Incorrect 139 ms 416 KB Output isn't correct
15 Incorrect 159 ms 504 KB Output isn't correct
16 Incorrect 177 ms 504 KB Output isn't correct
17 Incorrect 93 ms 384 KB Output isn't correct
18 Incorrect 147 ms 384 KB Output isn't correct
19 Incorrect 111 ms 384 KB Output isn't correct
20 Incorrect 170 ms 384 KB Output isn't correct
21 Incorrect 26 ms 384 KB Output isn't correct
22 Incorrect 52 ms 384 KB Output isn't correct
23 Incorrect 70 ms 384 KB Output isn't correct
24 Incorrect 72 ms 384 KB Output isn't correct
25 Incorrect 103 ms 384 KB Output isn't correct