Submission #1114686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114686		AdamGS	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	1 ms	336 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int MAX=2*1e5+7;

int pref[MAX];
int suf[MAX];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    queue<int> indeksy;

    pref[0] = 0;
    for (int i=1; i<=n; i++){
        if (s[i-1]=='J') indeksy.push(i);
        
        if ((int)indeksy.size()<k) pref[i] = -1;
        else if ((int)indeksy.size()==k) pref[i] = i-indeksy.front()-k+1;
        else{
            indeksy.pop();
            pref[i] = i-indeksy.front()-k+1;
        }
    }
    
    indeksy = queue<int>{};
    reverse(s.begin(), s.end());

    suf[n+1] = 0;
    for (int i=0; i<n; i++){
        if (s[i]=='I') indeksy.push(i);
        
        if ((int)indeksy.size()<k) suf[n-i] = -1;
        else if ((int)indeksy.size()==k) suf[n-i] = i-indeksy.front()-k+1;
        else{
            indeksy.pop();
            suf[n-i] = i-indeksy.front()-k+1;
        }
    }

    reverse(s.begin(), s.end());

    //for (int i=0; i<=n; i++) cout << i << " " << pref[i] << " " << suf[i] << endl;

    indeksy = queue<int>{};
    int kon=1, wyn=1e9;

    if (s[0]=='O') indeksy.push(0);

    while (kon<=n){
        kon++;
        if (s[kon-1]=='O') indeksy.push(kon);

        if ((int)indeksy.size() > k) indeksy.pop();

        if ((int)indeksy.size() == k){
            if ((pref[indeksy.front()-1] == -1) or (suf[kon+1] == -1)) continue;
            wyn = min(wyn, pref[indeksy.front()-1]+(kon-indeksy.front()-k+1)+suf[kon+1]);
        }
    }

    if (wyn==1e9) cout << "-1\n";
    else cout << wyn << "\n";

    return 0;
}

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