Submission #703856

#	Time	Username	Problem	Language	Result	Execution time	Memory
703856		asdfasdfasdfasdf	Round words (IZhO13_rowords)	C++14	100 / 100	32 ms	992 KiB

rowords

#include <bits/stdc++.h>

using namespace std;

int now_ih[4444];
int pre_ih[4444];
int now_iv[4444];
int pre_iv[4444];

vector<vector<int>> tree;

const int sz = 1 << 12;

string A,B;
int n,m;

int answer=0;

void add(int idx,int value)
{
    tree[idx].clear();
    idx|=sz;
    tree[idx].push_back(value);
    return;
}

int query(int l,int r,int k)
{
    l|=sz;
    r|=sz;
    int ret=0;
    while(l<=r)
    {
        if(l&1)
            ret+=upper_bound(tree[l].begin(),tree[l].end(),k)-tree[l].begin(),l++;
        if(~r&1)
            ret+=upper_bound(tree[r].begin(),tree[r].end(),k)-tree[r].begin(),r--;
        l>>=1;
        r>>=1;
    }
    return ret;
}

void fill_pre()
{
    for(int i=0;i<=2*m;i++)
    {
        pre_ih[i]=now_ih[i];
        pre_iv[i]=now_iv[i];
        now_ih[i]=0;
        now_iv[i]=0;
    }
    return;
}

void init()
{
    tree.clear();
    tree.resize(sz*2);
    for(int i=0;i<=2*m;i++)
        pre_ih[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=2*m;j++)
        {
            if(A[i]==B[j])
            {
                now_ih[j]=now_iv[j-1];
                now_iv[j]=pre_ih[j];
            }
            else
            {
                now_ih[j]=max(now_iv[j-1],pre_ih[j]);
                now_iv[j]=min(now_iv[j-1],pre_ih[j]);
            }
        }
        fill_pre();
    }

    for(int i=1;i<=2*m;i++)
        add(i,pre_ih[i]);

    for(int i=sz-1;i;i--)
    {
        tree[i].clear();
        tree[i].resize(tree[i*2].size()+tree[i*2+1].size());
        merge(tree[i*2].begin(),tree[i*2].end(),tree[i*2+1].begin(),tree[i*2+1].end(),tree[i].begin());
    }

    return;
}

void solve()
{
    for(int i=0;i<=m;i++)
        answer=max(answer,query(i+1,i+m,i));

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string a,b;
    cin >> a;
    cin >> b;
    n=b.size();
    m=a.size();


    A=" ";
    B=" ";

    B+=a;
    B+=a;
    A+=b;

    init();
    solve();

    reverse(a.begin(),a.end());

    B=" ";
    B+=a;
    B+=a;

    init();
    solve();

    cout << answer;
    return 0;
}

• Subtask 1: 100 / 100