제출 #1302928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302928		Petrix	원형 문자열 (IZhO13_rowords)	C++20	100 / 100	75 ms	125756 KiB

rowords

#include <iostream>
#include <algorithm>
using namespace std;

#define int long long

string s,s1;
int st[2001][4001];
int dr[2001][4001];
int n,m;

int solve(){
    int i,j,rasp=0,cnt;
    for(i=0;i<=2000;i++){
        for(j=0;j<=4000;j++){
            st[i][j]=dr[i][j]=0;
        }
    }
    for(i=1;i<=m;i++) dr[0][i]=i;
	for(i=1;i<=n;i++){
        for(j=1;j<=m;j++) {
            if(s[i]==s1[j]){
                dr[i][j]=st[i][j-1];
                st[i][j]=dr[i-1][j];
            }else{
                dr[i][j]=max(st[i][j-1],dr[i-1][j]);
                st[i][j]=min(st[i][j-1],dr[i-1][j]);
            }
        }
	}
	for(i=1;i<=m/2;i++) {
		cnt=0;
		for(j=i;j<=i+m/2-1;j++){
            if(dr[n][j]<=i-1) cnt++;
		}
		rasp=max(rasp,cnt);
	}
	return rasp;
}

signed main()
{
    int rasp;
    cin>>s>>s1;
	n=s.size();m=2*s1.size();
	s=" "+s;s1=" "+s1+s1;
	rasp=solve();
	reverse(s1.begin()+1,s1.begin()+m+1);
	rasp=max(rasp,solve());
	cout<<rasp;
    return 0;
}

• Subtask 1: 100 / 100