Submission #684258

# Submission time Handle Problem Language Result Execution time Memory
684258 2023-01-20T18:49:05 Z pragmatist Round words (IZhO13_rowords) C++17
8 / 100
2000 ms 12068 KB
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/

#include<bits/stdc++.h>
 
#define ld long double
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)3e4 + 7; // make sure this is right
const int M = (int)2e3 + 7;
const int inf = (int)2e9 + 7;
const ll INF = (ll)3e18 + 7; 
const double PI = acos(-1);
ll MOD = (ll)1e9 + 7; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

string s, t, S, T;

int dp[4003][4003];

void solve() {
	cin >> s >> t;
	int n = sz(s), m = sz(t);
	s = '#' + s;
	S = s;
	t = '#' + t;
	T = t;
	int ans = 0;
	for(int x = 0; x < n; ++x) {
		string w;
		for(int i = n - x + 1; i <= n; ++i) w += S[i];
		for(int i = 1; i <= n - x; ++i) w += S[i];
		s = '#' + w; 
		for(int y = 0; y < m; ++y) {
		    string h;
		    for(int i = m - y + 1; i <= m; ++i) h += T[i];
		    for(int i = 1; i <= m - x; ++i) h += T[i];
		    t = 'w' + h;
			for(int i = 1; i <= n; ++i) {
				for(int j = 1; j <= m; ++j) {
					if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
					else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
			ans = max(ans, dp[n][m]);   
		}
	}
	cout << ans << "\n";
}

signed main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen("g.in", "r", stdin);
//	freopen("g.out", "w", stdout);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 22 ms 520 KB Output isn't correct
5 Incorrect 4 ms 468 KB Output isn't correct
6 Execution timed out 2074 ms 4692 KB Time limit exceeded
7 Execution timed out 2079 ms 8276 KB Time limit exceeded
8 Execution timed out 2083 ms 8276 KB Time limit exceeded
9 Execution timed out 2078 ms 8276 KB Time limit exceeded
10 Execution timed out 2073 ms 8276 KB Time limit exceeded
11 Execution timed out 2079 ms 9044 KB Time limit exceeded
12 Execution timed out 2076 ms 10148 KB Time limit exceeded
13 Execution timed out 2086 ms 10068 KB Time limit exceeded
14 Execution timed out 2089 ms 9392 KB Time limit exceeded
15 Execution timed out 2081 ms 10580 KB Time limit exceeded
16 Execution timed out 2075 ms 8992 KB Time limit exceeded
17 Execution timed out 2079 ms 9632 KB Time limit exceeded
18 Execution timed out 2075 ms 11548 KB Time limit exceeded
19 Execution timed out 2082 ms 8276 KB Time limit exceeded
20 Execution timed out 2061 ms 10348 KB Time limit exceeded
21 Execution timed out 2080 ms 8164 KB Time limit exceeded
22 Execution timed out 2077 ms 9364 KB Time limit exceeded
23 Execution timed out 2071 ms 10200 KB Time limit exceeded
24 Execution timed out 2080 ms 10652 KB Time limit exceeded
25 Execution timed out 2078 ms 12068 KB Time limit exceeded