oj.uz

Submission #250907

# Submission time Handle Problem Language Result Execution time Memory
250907 2020-07-19T12:03:57 Z srvlt Round words (IZhO13_rowords) C++14
12 / 100
 158 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 = -inf, d2 = -inf;
	}
	void upd(const T & t) {
		if (t.len + 1 > len || (t.len == len && (max(0, t.d1) + 1 < d1 || max(0, t.d2) + 1 < d2))) {
			len = t.len + 1;
			d1 = max(0, t.d1) + 1;
			d2 = max(0, t.d2) + 1;
		}
	}
	void mx(const T & t) {
		if (t.len > len || (t.len == len && (t.d1 + 1 < d1 || t.d2 + 1 < d2))) {
			len = t.len;
			d1 = t.d1 + 1;
			d2 = t.d2 + 1;
		}
	}
};
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 (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
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 0 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 9 ms 384 KB Output isn't correct
7 Correct 46 ms 420 KB Output is correct
8 Incorrect 140 ms 504 KB Output isn't correct
9 Incorrect 133 ms 508 KB Output isn't correct
10 Incorrect 107 ms 504 KB Output isn't correct
11 Incorrect 106 ms 416 KB Output isn't correct
12 Incorrect 88 ms 384 KB Output isn't correct
13 Incorrect 158 ms 384 KB Output isn't correct
14 Incorrect 122 ms 384 KB Output isn't correct
15 Incorrect 137 ms 384 KB Output isn't correct
16 Incorrect 150 ms 384 KB Output isn't correct
17 Incorrect 78 ms 384 KB Output isn't correct
18 Incorrect 134 ms 504 KB Output isn't correct
19 Incorrect 101 ms 384 KB Output isn't correct
20 Incorrect 146 ms 384 KB Output isn't correct
21 Incorrect 22 ms 504 KB Output isn't correct
22 Incorrect 42 ms 384 KB Output isn't correct
23 Incorrect 59 ms 384 KB Output isn't correct
24 Incorrect 61 ms 408 KB Output isn't correct
25 Incorrect 81 ms 384 KB Output isn't correct