제출 #959511

#제출 시각아이디문제언어결과실행 시간메모리
959511OIaspirant2307JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
26 ms3560 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<int> preJ(n, 0), preO(n, 0), preI(n, 0);
    preJ[0] = (s[0] == 'J');
    preO[0] = (s[0] == 'O');
    preI[0] = (s[0] == 'I');

    for (int i = 1; i < n; i++)
    {
        preJ[i] = preJ[i - 1] + (s[i] == 'J');
        preO[i] = preO[i - 1] + (s[i] == 'O');
        preI[i] = preI[i - 1] + (s[i] == 'I');
    }

    int ans = n + 1;
    for (int i = 0; i < n; i++)
    {
        int x = lower_bound(preJ.begin(), preJ.end(), i + 1) - preJ.begin();
        int J = lower_bound(preJ.begin(), preJ.end(), i + k) - preJ.begin();
        if (J >= n)
            continue;
        int O = lower_bound(preO.begin(), preO.end(), preO[J] + k) - preO.begin();
        if (O >= n)
            continue;
        int I = lower_bound(preI.begin(), preI.end(), preI[O] + k) - preI.begin();
        if (I >= n)
            continue;
        ans = min(ans, I - x + 1 - 3 * k);
    }

    cout << (ans == n + 1 ? -1 : ans) << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...