Submission #1151430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151430		tvgk	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	5 ms	3804 KiB

ho_t2

#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;
}

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