Submission #1092995

#TimeUsernameProblemLanguageResultExecution timeMemory
1092995ortsacJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
32 ms3308 KiB
#include <bits/stdc++.h>

using namespace std;

string w = "JOI";
int n, k;
string s;
vector<array<int, 3>> pf;

int pTem(int start, int b) {
    int l = start, r = n, ans = n + 1;
    while (l <= r) {
        int m = (l+r)/2;
        int qtd = (pf[m][b] - pf[start - 1][b]);
        if (qtd >= k) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

int INF = 0x3f3f3f3f;

int32_t main() {
    //freopen("in", "r", stdin);
    cin >> n >> k >> s;
    pf.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        pf[i] = pf[i - 1];
        for (int j = 0; j < 3; j++) {
            if (s[i - 1] == w[j]) pf[i][j]++;
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        int a = pTem(i, 0);
        int b = pTem(a, 1);
        int c = pTem(b, 2);
        if (c == (n + 1)) continue;
        ans = min(ans, c - i + 1 - 3*k);
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...