oj.uz

Submission #205080

# Submission time Handle Problem Language Result Execution time Memory
205080 2020-02-27T20:49:29 Z moonrabbit2 Round words (IZhO13_rowords) C++17
0 / 100
 90 ms 131076 KB 
#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],ans[2*N][2*N],D[N][2*N],A[2*N],res;
void solve(){
    memset(V,0,sizeof(V));
    memset(H,0,sizeof(H));
    memset(ans,0,sizeof(ans));
    memset(D,0,sizeof(D));
    memset(A,0,sizeof(A));
    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]);
        }
    }
    D[0][0]=1;
    for(int i=1;i<=m;i++){
        assert(H[n][i]<=i);
        if(H[n][i]==0) D[0][i]=1;
        else A[H[n][i]]=i;
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=m;j++) if(i-1!=j) D[i][j]=D[i-1][j];
        D[i][A[i]]=1;
    }
    for(int i=0;i<=m;i++) 
        for(int j=i+1;j<=m;j++) ans[i][j]=ans[i][j-1]+D[i][j];
    for(int i=1;i<=k;i++) res=max(res,ans[i-1][i+k-1]);
}
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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 83 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 83 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 86 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 86 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 84 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 83 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 84 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 88 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 82 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 84 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 82 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 80 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 82 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 83 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 84 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 87 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 84 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 90 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 80 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 89 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)