Submission #1180654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180654		takoshanava	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	11 ms	3092 KiB

ho_t2

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

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

    vector<int> posj, poso, posi;

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'J') posj.pb(i);
        else if (s[i] == 'O') poso.pb(i);
        else if (s[i] == 'I') posi.pb(i);
    }

    int ans = 1e9;

    for (int j = 0; j + k - 1 < posj.size(); ++j) {
        int jend = posj[j + k - 1];

        auto o = lower_bound(poso.begin(), poso.end(), jend + 1);
        if (o + k - 1 >= poso.end()){
            continue;
        }

        int oend = *(o + k - 1);

        auto i = lower_bound(posi.begin(), posi.end(), oend + 1);
        if (i + k - 1 >= posi.end()){
            continue;
        }

        int iend = *(i + k - 1);

        int len = iend - posj[j] + 1;
        int cost = len - 3 * k;
        ans = min(ans, cost);
    }

    if(ans == 1e9){
        cout << -1;
        return 0;
    }

    cout << ans;
}

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