Submission #205399

#	Time	Username	Problem	Language	Result	Execution time	Memory
205399		moonrabbit2	Round words (IZhO13_rowords)	C++17	100 / 100	74 ms	63480 KiB

rowords

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
const ll mod=998244353,inf=1e18;
const int N=2005,M=1e6+5,K=1e5+5;
string s,t;
int n,m,k,V[N][2*N],H[N][2*N],res,ans;
void solve(){
    memset(V,0,sizeof(V));
    memset(H,0,sizeof(H));
    for(int i=1;i<=m;i++) H[0][i]=i;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        if(s[i]==t[j]){
            H[i][j]=V[i][j-1];
            V[i][j]=H[i-1][j];
        } else{
            H[i][j]=max(V[i][j-1],H[i-1][j]);
            V[i][j]=min(V[i][j-1],H[i-1][j]);
        }
    }
    for(int i=1;i<=k;i++){
        ans=0;
        for(int j=i;j<=i+k-1;j++) if(H[n][j]<=i-1) ans++;
        res=max(res,ans);
    }
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
    cin>>s>>t;
    n=s.size(); k=t.size(); m=2*k; s=" "+s; t=" "+t+t;
    solve();
    reverse(t.begin()+1,t.begin()+1+m);
    solve();
    cout<<res;
    return 0;
}

• Subtask 1: 100 / 100