oj.uz

Submission #684234

# Submission time Handle Problem Language Result Execution time Memory
684234 2023-01-20T18:07:59 Z pragmatist Round words (IZhO13_rowords) C++17
28 / 100
 2000 ms 11872 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;

int dp[4003][4003];

void solve() {
	cin >> s >> t;
	int n = sz(s), m = sz(t);
	s = '#' + s;
	S = s;
	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 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;
}

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 191 ms 4736 KB Output is correct
7 Execution timed out 2094 ms 8276 KB Time limit exceeded
8 Incorrect 1636 ms 8276 KB Output isn't correct
9 Execution timed out 2053 ms 8276 KB Time limit exceeded
10 Execution timed out 2085 ms 8276 KB Time limit exceeded
11 Execution timed out 2075 ms 9044 KB Time limit exceeded
12 Correct 1437 ms 10152 KB Output is correct
13 Execution timed out 2064 ms 10068 KB Time limit exceeded
14 Execution timed out 2083 ms 9300 KB Time limit exceeded
15 Execution timed out 2074 ms 10580 KB Time limit exceeded
16 Execution timed out 2069 ms 8976 KB Time limit exceeded
17 Execution timed out 2093 ms 9300 KB Time limit exceeded
18 Execution timed out 2097 ms 11348 KB Time limit exceeded
19 Execution timed out 2093 ms 8276 KB Time limit exceeded
20 Execution timed out 2073 ms 10196 KB Time limit exceeded
21 Correct 1219 ms 8164 KB Output is correct
22 Execution timed out 2062 ms 9368 KB Time limit exceeded
23 Execution timed out 2068 ms 10068 KB Time limit exceeded
24 Execution timed out 2075 ms 10580 KB Time limit exceeded
25 Execution timed out 2064 ms 11872 KB Time limit exceeded