Submission #1131522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131522		lopkus	JJOOII 2 (JOI20_ho_t2)	C++20	0 / 100	0 ms	320 KiB

ho_t2

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    vector<int> idx[4];
    for(int i = 1; i <= n; i++) {
        char x;
        cin >> x;
        if(x == 'J') {
            a[i] = 1;
        }
        else if(x == 'O') {
            a[i] = 2;
        }
        else {
            a[i] = 3;
        }
        idx[a[i]].push_back(i);
    }
    vector<int> cnt1(n + 1, 0);
    vector<int> cnt2(n + 1, 0);
    vector<int> cnt3(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        cnt1[i] = cnt1[i - 1];
        cnt2[i] = cnt2[i - 1];
        cnt3[i] = cnt3[i - 1];
        if(a[i] == 1) {
            cnt1[i] += 1;
        }
        else if(a[i] == 2) {
            cnt2[i] += 1;
        }
        else {
            cnt3[i] += 1;
        }
    }
    int ans = n + 1;
    for(int i = 0; i + k - 1 < idx[1].size(); i++) {
        int l1 = idx[1][i];
        int r1 = idx[1][i + k - 1];
        int l2 = - 1;
        int r2 = - 1;
        for(int j = 0; j + k - 1 < idx[2].size(); j++) {
            if(idx[2][j] >= r1) {
                l2 = idx[2][j];
                r2 = idx[2][j + k - 1];
            }
        }
        int l3 = - 1;
        int r3 = - 1;
        for(int j = 0; j + k - 1 < idx[3].size(); j++) {
            if(idx[3][j] >= r2) {
                l3 = idx[3][j];
                r3 = idx[3][j + k - 1];
            }
        }
        if(l2 == - 1 || l3 == - 1) {
            continue;
        }
        int u = 0;
        u += (r1 - l1 + 1) - (cnt1[r1] - cnt1[l1 - 1]);
        u += l2 - r1 - 1;
        u += (r2 - l2 + 1 ) - (cnt2[r2] - cnt2[l2 - 1]);
        u += l3 - r2 - 1;
        u += (r3 - l3 + 1 ) - (cnt3[r3] - cnt3[l3 - 1]);
        ans = min(ans, u);
    }
    if(ans == n + 1) {
        cout << - 1;
    }
    else {
        cout << ans;
    }
}

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