Submission #440478

# Submission time Handle Problem Language Result Execution time Memory
440478 2021-07-02T10:14:32 Z dutch Round words (IZhO13_rowords) C++17
16 / 100
39 ms 11116 KB
#include <bits/stdc++.h>
using namespace std;

int n, m;
string a, b;

vector<vector<int>> get(){
	a = '_' + a;
	b = '-' + b;
	vector<vector<int>> dp(n+1, vector<int> (m+1));

	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j){
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			if(a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
		}
	}
	a.erase(a.begin());
	b.erase(b.begin());

	return dp;
}

int solve(){
	vector<vector<int>> x, y;
	x = get();
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	y = get();
	reverse(b.begin(), b.end());


	int res = 0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=m; ++j)
			res = max(res, x[i][m-j] + y[n-i][m]);

	return res;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> a >> b;
	n = a.size(), m = b.size();
	cout << max(solve(), solve());
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Incorrect 3 ms 1100 KB Output isn't correct
7 Correct 25 ms 8232 KB Output is correct
8 Incorrect 28 ms 8252 KB Output isn't correct
9 Incorrect 27 ms 8248 KB Output isn't correct
10 Incorrect 26 ms 8156 KB Output isn't correct
11 Incorrect 28 ms 9036 KB Output isn't correct
12 Incorrect 39 ms 10480 KB Output isn't correct
13 Incorrect 35 ms 10476 KB Output isn't correct
14 Incorrect 29 ms 9420 KB Output isn't correct
15 Incorrect 35 ms 11116 KB Output isn't correct
16 Incorrect 30 ms 9060 KB Output isn't correct
17 Incorrect 24 ms 6900 KB Output isn't correct
18 Incorrect 34 ms 10580 KB Output isn't correct
19 Incorrect 27 ms 8156 KB Output isn't correct
20 Incorrect 31 ms 9620 KB Output isn't correct
21 Incorrect 7 ms 2380 KB Output isn't correct
22 Incorrect 11 ms 3896 KB Output isn't correct
23 Incorrect 16 ms 5424 KB Output isn't correct
24 Incorrect 17 ms 5688 KB Output isn't correct
25 Incorrect 24 ms 7564 KB Output isn't correct