Submission #250920

#	Time	Username	Problem	Language	Result	Execution time	Memory
250920		srvlt	원형 문자열 (IZhO13_rowords)	C++14	28 / 100	179 ms	508 KiB

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))) {
			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;
}

• Subtask 1: 28 / 100