Submission #250898

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
250898	2020-07-19T11:27:29 Z	srvlt	Round words (IZhO13_rowords)	C++14	12 / 100	156 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;

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

int LCS(const string & a, const string & b) {
	int n = SZ(a), m = SZ(b);
	int can = min(n, m) / 2;
	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 (a[i - 1] == b[j - 1])
				dp[j].upd(dp[j - 1]);
		}
		for (int j = 1; j <= m; j++)
			dp[j].max(dp[j - 1]);
		for (int j = 1; j <= m; j++)
			if (dp[j].d >= can) 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

12.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	384 KB	Output isn't correct
2	Incorrect	0 ms	384 KB	Output isn't 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	Incorrect	8 ms	384 KB	Output isn't correct
7	Correct	45 ms	504 KB	Output is correct
8	Incorrect	111 ms	384 KB	Output isn't correct
9	Incorrect	120 ms	384 KB	Output isn't correct
10	Incorrect	104 ms	384 KB	Output isn't correct
11	Incorrect	100 ms	384 KB	Output isn't correct
12	Incorrect	85 ms	384 KB	Output isn't correct
13	Incorrect	156 ms	416 KB	Output isn't correct
14	Incorrect	114 ms	384 KB	Output isn't correct
15	Incorrect	134 ms	384 KB	Output isn't correct
16	Incorrect	146 ms	384 KB	Output isn't correct
17	Incorrect	76 ms	384 KB	Output isn't correct
18	Incorrect	120 ms	384 KB	Output isn't correct
19	Incorrect	91 ms	384 KB	Output isn't correct
20	Incorrect	133 ms	384 KB	Output isn't correct
21	Incorrect	22 ms	384 KB	Output isn't correct
22	Incorrect	39 ms	384 KB	Output isn't correct
23	Incorrect	55 ms	384 KB	Output isn't correct
24	Incorrect	58 ms	408 KB	Output isn't correct
25	Incorrect	80 ms	504 KB	Output isn't correct