제출 #1299717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1299717		azamurai	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	6 ms	3012 KiB

ho_t2

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

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