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

rowords

#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());
}

Subtask #1

16.0 / 100.0

#	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