Submission #1254623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254623		LeonaRaging	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	9352 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 2e5 + 4;
const int INF = 1e9;

int n, k, cnt[3], cost[maxn][3], nxt[maxn][2];
string s;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k >> s;
    int R1 = -1, R2 = -1, R3 = -1;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cost[i][j] = INF;
    for (int L = 0; L < n; L++) {
        while (R1 + 1 < n && cnt[0] < k) {
            R1++;
            if (s[R1] == 'J') cnt[0]++;
        }
        if (cnt[0] == k) {
            cost[L][0] = R1 - L + 1 - k;
            nxt[L][0] = R1 + 1;
        }
        else nxt[L][0] = n;
        while (R2 + 1 < n && cnt[1] < k) {
            R2++;
            if (s[R2] == 'O') cnt[1]++;
        }
        if (cnt[1] == k) {
            cost[L][1] = R2 - L + 1 - k;
            nxt[L][1] = R2 + 1;
        }
        else nxt[L][1] = n;
        while (R3 + 1 < n && cnt[2] < k) {
            R3++;
            if (s[R3] == 'I') cnt[2]++;
        }
        if (cnt[2] == k) {
            cost[L][2] = R3 - L + 1 - k;
        }
        if (s[L] == 'J') cnt[0]--;
        if (s[L] == 'O') cnt[1]--;
        if (s[L] == 'I') cnt[2]--;
    }
    int res = INF;
    for (int i = 0; i < n; i++) {
        int j = nxt[i][0], k = nxt[nxt[i][0]][1];
        res = min(res, cost[i][0] + cost[j][1] + cost[k][2]);
    }
    cout << (res == INF ? -1 : res) << '\n';
}

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