Submission #554796

#	Time	Username	Problem	Language	Result	Execution time	Memory
554796		andrei_boaca	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	180 ms	70172 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;
int n,k;
int v[200005],dp[200005][4][22];
int move(int poz,int nr)
{
    int rez=poz;
    int need=k;
    if(nr==1)
        need-=1;
    for(int bit=0;bit<=20;bit++)
        if((need>>bit)&1)
            rez=dp[rez][nr][bit];
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        if(c=='J')
            v[i]=1;
        if(c=='O')
            v[i]=2;
        if(c=='I')
            v[i]=3;
    }
    for(int i=n;i>=1;i--)
    {
        for(int nr=1;nr<=3;nr++)
        {
            if(v[i+1]==nr)
                dp[i][nr][0]=i+1;
            else
                dp[i][nr][0]=dp[i+1][nr][0];
            for(int j=1;j<=20;j++)
                dp[i][nr][j]=dp[dp[i][nr][j-1]][nr][j-1];
        }
    }
    int ans=1e9;
    for(int i=1;i<=n;i++)
        if(v[i]==1)
        {
            int poz=i;
            poz=move(poz,1);
            poz=move(poz,2);
            poz=move(poz,3);
            if(poz>0&&poz<=n)
                ans=min(ans,poz-i+1-k*3);
        }
    if(ans==1e9)
        cout<<-1;
    else
        cout<<ans;
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87