Submission #1336905

#TimeUsernameProblemLanguageResultExecution timeMemory
1336905kawhietJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
11 ms4800 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<vector<int>> p(3, vector<int>(n + 1));
    string t = "JOI";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            p[i][j + 1] = p[i][j] + (s[j] == t[i]);
        }
    }
    vector<int> pos, ls, rs;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'O') {
            pos.push_back(i);
        } else if (s[i] == 'J') {
            ls.push_back(i);
        } else {
            rs.push_back(i);
        }
    }
    int ans = n;
    for (int i = 0; i + k <= pos.size(); i++) {
        int l = ranges::upper_bound(ls, pos[i]) - ls.begin() - k;
        if (l < 0) continue;
        int r = ranges::upper_bound(rs, pos[i + k - 1]) - rs.begin() + k - 1;
        if (r >= rs.size()) continue;
        ans = min(ans, rs[r] - ls[l] + 1 - 3 * k);
    }
    cout << (ans == n ? -1 : ans) << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...