Submission #936699

#	Time	Username	Problem	Language	Result	Execution time	Memory
936699		kitlix	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	25 ms	7396 KiB

ho_t2

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

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