제출 #1086506

#제출 시각아이디문제언어결과실행 시간메모리
1086506toast12JJOOII 2 (JOI20_ho_t2)C++14
100 / 100
20 ms3328 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...