Submission #390747

#	Time	Username	Problem	Language	Result	Execution time	Memory
390747		timmyfeng	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	9 ms	2944 KiB

ho_t2

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

const int N = 200001;

int nxt[3][N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    string s;
    cin >> n >> k >> s;

    for (int i = 0; i < 3; ++i) {
        int count = 0;
        for (int l = 0, r = 0; l < n; ++l) {
            while (count < k && r < n) {
                count += s[r++] == "JOI"[i];
            }
            nxt[i][l] = r + (count < k);
            count -= s[l] == "JOI"[i];
        }
        nxt[i][n] = n + 1;
    }

    int ans = n + 1;
    for (int l = 0; l < n; ++l) {
        int r = l;
        for (int i = 0; i < 3 && r <= n; ++i) {
            r = nxt[i][r];
        }
        if (r <= n) {
            ans = min(ans, r - l - 3 * k);
        }
    }

    cout << (ans <= n ? ans : -1) << "\n";
}

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