Submission #1234200

#TimeUsernameProblemLanguageResultExecution timeMemory
1234200marJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
19 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    string s;
    s.resize(n + 1);
    for (int i = 1; i <= n; ++i) cin >> s[i];

    vector<int> posj, poso, posi;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'J') posj.push_back(i);
        else if (s[i] == 'O') poso.push_back(i);
        else if (s[i] == 'I') posi.push_back(i);
    }

    int res = inf;

    for (int i = 1; i <= n; ++i) {
        int curpos = i - 1;
        int idx = (int)(lower_bound(posj.begin(), posj.end(), curpos + 1) - posj.begin());
        if (idx + k - 1 >= (int)posj.size()) continue;
        curpos = posj[idx + k - 1];

        idx = (int)(lower_bound(poso.begin(), poso.end(), curpos + 1) - poso.begin());
        if (idx + k - 1 >= (int)poso.size()) continue;
        curpos = poso[idx + k - 1];

        idx = (int)(lower_bound(posi.begin(), posi.end(), curpos + 1) - posi.begin());
        if (idx + k - 1 >= (int)posi.size()) continue;
        curpos = posi[idx + k - 1];

        res = min(res, curpos - i + 1 - 3 * k);
    }

    if (res == inf) cout << "-1\n";
    else cout << res << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...