Submission #1250969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250969		gry3125	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	7 ms	2388 KiB

ho_t2

#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;

int main() {
    int n, k; string s;
    cin >> n >> k >> s;
    vector<int> ji, ii, po(n+1);
    for (int i = 1; i <= n; i++) {
        if (s[i-1] == 'J') ji.pb(i);
        if (s[i-1] == 'I') ii.pb(i);
        po[i] = po[i-1];
        if (s[i-1] == 'O') po[i]++;
    }
    int L = 0, R = 0; int mn = 1000000;
    while (L+k-1 < ji.size() && R+k-1 < ii.size()) {
        while (R+k-1 < ii.size() && (ji[L+k-1] > ii[R] || po[ii[R]]-po[ji[L+k-1]-1] < k)) {
            R++;
        }
        if (R+k-1 < ii.size() && !(ji[L+k-1] > ii[R] || po[ii[R]]-po[ji[L+k-1]-1] < k)) {
        	mn = min(mn, ii[R+k-1]-ji[L]+1-3*k);
        }
        L++;
    }
    if (mn == 1000000) mn = -1;
    cout << mn;
    return 0;
}

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