Submission #1086506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086506		toast12	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	20 ms	3328 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> jpos(n+1), opos(n+1), ipos(n+1);
    for (int l = 1; l <= n; l++) {
        jpos[l] = jpos[l-1], ipos[l] = ipos[l-1], opos[l] = opos[l-1];
        if (s[l-1] == 'J') jpos[l]++;
        if (s[l-1] == 'O') opos[l]++;
        if (s[l-1] == 'I') ipos[l]++;
    }
    int ans = INT_MAX;
    for (int j = 0; j < n; j++) {
        int x = j;
        int a = lower_bound(jpos.begin()+x, jpos.end(), jpos[x]+k) - jpos.begin();
        if (a > n) break;
        int b = lower_bound(opos.begin()+a, opos.end(), opos[a]+k) - opos.begin();
        if (b > n) break;
        int c = lower_bound(ipos.begin()+b, ipos.end(), ipos[b]+k) - ipos.begin();
        if (c > n) break;
        ans = min(ans, (c-x)-(3*k));
    }
    if (ans == INT_MAX) ans = -1;
    cout << ans << '\n';
    return 0;
}

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