Submission #349921

#	Time	Username	Problem	Language	Result	Execution time	Memory
349921		shivensinha4	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	28 ms	13304 KiB

ho_t2

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

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