제출 #349921

#제출 시각아이디문제언어결과실행 시간메모리
349921shivensinha4JJOOII 2 (JOI20_ho_t2)C++17
100 / 100
28 ms13304 KiB
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'


int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k; cin >> n >> k;
    string s; cin >> s;
    vector<vi> pref(n, vi(3));
    for_(i, 0, n) {
        if (s[i] == 'J') pref[i][0]++;
        else if (s[i] == 'O') pref[i][1]++;
        else pref[i][2]++;
    }

    for_(i, 1, n) for_(j, 0, 3) pref[i][j] += pref[i-1][j];

    vi pre(n), curr(n);
    for_(i, 0, n) pre[i] = i;

    for (int j = 2; j >= 0; j--) {
        curr.assign(n, n);
        int pt = n;
        for (int i = n-1; i >= 0; i--) {
            while (pt > i and pref[pt-1][j] - (i > 0 ? pref[i-1][j] : 0) >= k) pt--;
            curr[i] = pt;
            if (pt != n) curr[i] = pre[pt];
        }

        swap(curr, pre);
    }

    int ans = n;
    for_(i, 0, n) if (pre[i] != n) ans = min(ans, pre[i]-i+1-3*k);
    cout << (ans == n ? -1 : ans) << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...