제출 #936699

#제출 시각아이디문제언어결과실행 시간메모리
936699kitlixJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
25 ms7396 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 1e9;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<vector<int>> pref(3, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        if (i)
            for (int j = 0; j < 3; ++j)
                pref[j][i] = pref[j][i - 1];
        if (s[i] == 'J')
            pref[0][i] += 1;
        else if (s[i] == 'O')
            pref[1][i] += 1;
        else
            pref[2][i] += 1;
    }
    int ans = INF;
    for (int i = 0; i + 3 * k <= n; ++i) {
        int needid = i;
        for (int j = 0; j < 3; ++j) {
            int prval = (needid ? pref[j][needid - 1] : 0);
            int curid = lower_bound(pref[j].begin(), pref[j].end(), prval + k) - pref[j].begin();
            needid = max(needid, curid);
        }
        if (needid < n)
            ans = min(ans, (needid - i + 1) - 3 * k);
    }
    cout << (ans == INF ? -1 : ans);
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...