제출 #894202

#제출 시각아이디문제언어결과실행 시간메모리
894202boxJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
6 ms3556 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...