Submission #552618

#	Time	Username	Problem	Language	Result	Execution time	Memory
552618		RaresFelix	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	39 ms	3172 KiB

ho_t2

#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;
}

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