Submission #1299717

#TimeUsernameProblemLanguageResultExecution timeMemory
1299717azamuraiJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
6 ms3012 KiB
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second
#define mp make_pair
#define Sz(x) (int)x.size()

using namespace std;

const int N = 2e5 + 5;
int n, k, suf[N];
string s;

void solve() {
    cin >> n >> k >> s;
    vector <int> sj, so, si;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'J') sj.push_back(i);
        else if (s[i] == 'O') so.push_back(i);
        else si.push_back(i);
    }
    reverse(so.begin(), so.end());
    reverse(si.begin(), si.end());
    int ans = INT_MAX;
    for (int i = 0; i + k - 1 < Sz(sj); i++) {
        while (Sz(so) > 0 && so.back() <= sj[i + k - 1]) so.pop_back();
        if (Sz(so) < k) break;
        while (Sz(si) > 0 && si.back() <= so[Sz(so) - k]) si.pop_back();
        if (Sz(si) < k) break;
        int l = sj[i], r = si[Sz(si) - k];
        ans = min(ans, n - (l + (n - r - 1)) - 3 * k);
    }
    if (ans == INT_MAX) cout << -1;
    else cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin >> tt;

    while (tt--) {
        solve();
        // cout << '\n';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...