Submission #1247721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247721		inkvizytor	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	6 ms	3028 KiB

ho_t2

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

#define ll long long

void znajdz(string &s, int k, char c, vector<int> &t) {
    int b = 0, e = 0, l = (s[0]==c);
    while (e < (int)s.size()) {
        if (l < k) {
            e++;
            l += (s[e]==c);
        }
        else {
            t[b] = e;
            l -= (s[b]==c);
            b++;
        }
    }
    return;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<int> tj (n+10, n), to (n+10, n), ti (n+10, n);
    znajdz(s, k, 'J', tj);
    znajdz(s, k, 'O', to);
    znajdz(s, k, 'I', ti);
    int sc = 1e9;
    for (int i = 0; i < n; i++){
        int x = i;
        x = tj[x]+1;
        x = to[x]+1;
        x = ti[x];
        if (x < n) {
            sc = min(sc, n-k*3-i-(n-x-1));
        }
    }
    if (sc == (int)1e9) {
        cout << -1 << '\n';
    }
    else {
        cout << sc << '\n';
    }
}

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