Submission #1280886

#TimeUsernameProblemLanguageResultExecution timeMemory
1280886SSKMFJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
6 ms2460 KiB
#include <bits/stdc++.h>
using namespace std;

int minim[2][300001];
char sir[300001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , cantitate;
    cin >> lungime >> cantitate >> sir;

    for (auto dorit : {'J' , 'O' , 'I'})
    {
        queue <int> gasit;
        for (int indice = 0 ; indice <= lungime ; indice++)
        {
            if (sir[indice - 1] == dorit)
                { gasit.push(indice); }

            if ((int)gasit.size() > cantitate)
                { gasit.pop(); }

            if ((int)gasit.size() < cantitate || minim[0][gasit.front() - 1] == -1)
                { minim[1][indice] = -1; continue; }

            minim[1][indice] = minim[0][gasit.front() - 1] + indice - gasit.front() + 1;
        }

        for (int indice = 0 ; indice <= lungime ; indice++)
            { minim[0][indice] = minim[1][indice]; }
    }

    if (minim[1][lungime] == -1)
        { cout << "-1"; return 0; }
    
    int rezultat = INT32_MAX;
    for (int indice = 0 ; indice <= lungime ; indice++) {
        if (minim[1][indice] != -1)
            { rezultat = min(rezultat , minim[1][indice]); }
    }

    cout << rezultat - 3 * cantitate;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...