Submission #894202

#	Time	Username	Problem	Language	Result	Execution time	Memory
894202		box	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	6 ms	3556 KiB

ho_t2

#include "bits/stdc++.h"

using namespace std;

const int N = 2e5;
const string JOI = "JOI";

int n, k;
string s;
int jmp[3][N + 1];

int solve(int i) {
    i = jmp[0][i];
    i = jmp[1][i];
    i = jmp[2][i];
    return i == n ? -1 : i;
}

int main() {
    cin.tie(0)->sync_with_stdio(0), cin.exceptions(cin.failbit);
    cin >> n >> k >> s;
    for (int x = 0; x < 3; x++) {
        jmp[x][n] = n;
        for (int i = 0, j = 0, c = 0; i < n; i++) {
            while (j < n && c < k) c += s[j++] == JOI[x];
            jmp[x][i] = c == k ? j - 1 : n;
            c -= s[i] == JOI[x];
        }
    }
    int ans = n;
    for (int i = 0; i < n; i++) {
        int j = solve(i);
        if (j != -1) ans = min(ans, j - i + 1 - k * 3);
    }
    cout << (ans == n ? -1 : ans) << '\n';
}

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