제출 #339787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339787		amunduzbaev	원형 문자열 (IZhO13_rowords)	C++14	8 / 100	2090 ms	16640 KiB

rowords

/** made by amunduzbaev **/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int N = 2005;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, t, dp[N][N];

void solve(){
	string a, b;
	cin>>a>>b;
	int ans = 0;
	int cnta = 0, cntb = 0, aa = sz(a), bb = sz(b);
	while(cnta < aa){
		string tmpa = string(a.begin() + cnta, a.end()) + string(a.begin(), a.begin()+cnta);
		cntb = 0;
		while(cntb < bb){
			string tmpb = string(b.begin() + cntb, b.end()) + string(b.begin(), b.begin() + cntb);
			
			for(int i=0;i<aa;i++){
				for(int j=0;j<bb;j++){
					if(i && j && tmpa[i] == tmpb[j]) dp[i][j] += dp[i-1][j-1] +1;
					else if(tmpa[i] == tmpb[j]) dp[i][j]++;
					if(i) dp[i][j] = max(dp[i-1][j], dp[i][j]);
					if(j) dp[i][j] = max(dp[i][j-1], dp[i][j]);
					if(i && j) dp[i][j] = max(dp[i][j], dp[i-1][j-1]); 
				}
			}
			
			ans = max(ans, dp[aa-1][bb-1]);
			/*
			for(int i=0;i<aa;i++){
				for(int j=0;j<bb;j++) cout<<dp[i][j]<<" ";
				cout<<"\n";
			}cout<<"\n";
			*/
			memset(dp, 0, sizeof dp);
			cntb++;
		}
		cnta++;
	}
	cout<<ans<<'\n';
	return;
}

int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

• Subtask 1: 8 / 100