Submission #1151430

#TimeUsernameProblemLanguageResultExecution timeMemory
1151430tvgkJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
5 ms3804 KiB
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

int lst[3][mxN], n, k;
queue<int> q[3];
string s;
char chr[3] = {'J', 'O', 'I'};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> k;
    cin >> s;
    s = ' ' + s;

    int ans = inf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            lst[j][i] = lst[j][i - 1];

            if (s[i] != chr[j])
                continue;

            q[j].push(i);
            if (q[j].size() > k)
                q[j].pop();

            if (q[j].size() == k)
                lst[j][i] = q[j].front();
        }

        int cur = i;
        for (int j = 2; j >= 0; j--)
            cur = lst[j][cur];

        if (cur)
            ans = min(ans, i - cur + 1);
    }
    if (ans == inf)
        cout << -1;
    else
        cout << ans - 3 * k;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...