Submission #1280364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280364		ducanh0811	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	10 ms	7444 KiB

ho_t2

#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 200005
int n, k;
string s;
int prefj[MAXN];
int suffi[MAXN];
int prefo[MAXN];
const int inf = 1e16;
int pos[MAXN];
int prefmi[MAXN];

void solve(){
    cin >> n >> k;
    cin >> s;
    int ptr = 1;
    int sum = 0;
    int cnt = 0;
    FOR(i, 0, n + 1) prefj[i] = inf;
    FOR(i, 0, n + 1) suffi[i] = inf;
    FOR(i, 1, n){
        if (s[i - 1] == 'J') sum++;
            else cnt++;
        while (sum > k || s[ptr - 1] != 'J'){
            if (s[ptr - 1] == 'J') sum--;
                else cnt--;
            ptr++;
        }
        if (sum == k){
            prefj[i] = cnt;
        }
    }
    ptr = n;
    sum = 0;
    cnt = 0;
    REV(i, n, 1){
        if (s[i - 1] == 'I') sum++;
            else cnt++;
        while (sum > k || s[ptr - 1] != 'I') {
            if (s[ptr - 1] == 'I') sum--;
                else cnt--;
            ptr--;
        }
        if (sum == k) {
            suffi[i] = cnt;
        }
    }
    FOR(i, 1, n) {
        prefo[i] = prefo[i - 1];
        if (s[i - 1] == 'O') prefo[i]++;
        pos[prefo[i]] = i;
    }
    FOR(i, 0, n + 1) prefmi[i] = inf;
    FOR(i, 1, n){
        prefmi[i] = prefmi[i - 1];
        prefmi[i] = min(prefmi[i], - i - k + prefj[i]);
    }
    int res = inf;
    FOR(i, 1, n){
        if (prefo[i] < k) continue;
        int need = pos[prefo[i] - k];
        res = min(res, suffi[i + 1] + prefmi[need] + i);
    }
    if (res > inf / 10) res = -1;
    cout << res;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

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