제출 #440478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440478		dutch	원형 문자열 (IZhO13_rowords)	C++17	16 / 100	39 ms	11116 KiB

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 / 100