Submission #1092995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092995		ortsac	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	32 ms	3308 KiB

ho_t2

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

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