Submission #959511

#	Time	Username	Problem	Language	Result	Execution time	Memory
959511		OIaspirant2307	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	26 ms	3560 KiB

ho_t2

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

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