Submission #552618

#TimeUsernameProblemLanguageResultExecution timeMemory
552618RaresFelixJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
39 ms3172 KiB
#include <bits/stdc++.h>
#define MN 200071

using namespace std;
int n, k, F[3][MN];
inline int id (char c) {
    return c == 'I' ? 2 : c == 'O';
}

int solve(int p1) {
    int len = n - p1 + 1;
    int st = p1, dr = n, mij;
    for(int cul = 0; cul < 3; ++cul) {
        if(F[cul][n] - F[cul][p1-1] < k) return -1;
        st = p1, dr = n;
        while(st < dr) {
            mij = (st + dr) >> 1;
            if(F[cul][mij] - F[cul][p1-1] >= k) dr = mij;
            else st = mij + 1;
        }
        p1 = st + 1;
    }
    return len - (n - p1 + 1) - 3 * k;
}
string S;
int main() {
    cin >> n >> k >> S;
    for(int i = 1; i <= n; ++i) {
        ++F[id(S[i-1])][i];
        for(int d = 0; d < 3; ++d) F[d][i] += F[d][i-1];
    }
    int rez = -1, ac = 0;
    for(int i = 1; i <= n; ++i) {
        ac = solve(i);
        if(ac != -1) {
            if(rez == -1) rez = ac;
            else rez = min(rez, ac);
        }
    }
    cout << rez << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...