Submission #584054

#	Time	Username	Problem	Language	Result	Execution time	Memory
584054		sofijavelkovska	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	25 ms	3172 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, k, m=-1, x, y, z, t, i;
    string s;
    cin >> n >> k >> s;
    int aj[n], ao[n], ai[n];
    if (s[0]=='J')
    {
        aj[0]=1;
        ao[0]=1;
        ai[0]=1;
    }
    if (s[0]=='O')
    {
        aj[0]=0;
        ao[0]=1;
        ai[0]=0;
    }
    if (s[0]=='I')
    {
        aj[0]=0;
        ao[0]=0;
        ai[0]=1;
    }
    for (i=1; i<n; i++)
    {
        if (s[i]=='J')
            aj[i]=aj[i-1]+1;
        else
            aj[i]=aj[i-1];
    }
    for (i=1; i<n; i++)
    {
        if (s[i]=='O')
            ao[i]=ao[i-1]+1;
        else
            ao[i]=ao[i-1];
    }
    for (i=1; i<n; i++)
    {
        if (s[i]=='I')
            ai[i]=ai[i-1]+1;
        else
            ai[i]=ai[i-1];
    }
    for (i=0; i<n; i++)
        if (s[i]=='J')
        {
            //cout << i << " ";
            if (i!=0)
                t=k+aj[i-1];
            else
                t=k;
            x=lower_bound(aj, aj+n, t)-aj;
            //cout << x << " ";
            if (x==n)
                continue;
            t=k+ao[x];
            y=lower_bound(ao, ao+n, t)-ao;
            //cout << y << " ";
            if (y==n)
                continue;
            t=k+ai[y];
            z=lower_bound(ai, ai+n, t)-ai;
            //cout << z << endl;
            if (z==n)
                continue;
            if (m==-1 || z-i+1-3*k<m)
                m=z-i+1-3*k;
        }
    cout << m;

    return 0;
}

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