Submission #1174880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174880		Hamed_Ghaffari	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	9 ms	3340 KiB

ho_t2

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

const int MXN = 2e5+5;

int n, k, cj[MXN], ci[MXN];
vector<int> J, O, I;
string s;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k >> s;
    for(int i=0; i<n; i++) {
        cj[i] = (i?cj[i-1]:0) + (s[i]=='J');
        ci[i] = (i?ci[i-1]:0) + (s[i]=='I');
        if(s[i]=='J') J.push_back(i);
        if(s[i]=='O') O.push_back(i);
        if(s[i]=='I') I.push_back(i);
    }
    int ans = 10*n;
    for(int i=0; i<int(O.size())-k+1; i++)
        if(cj[O[i]]>=k && ci[n-1]-ci[O[i+k-1]]>=k)
            ans = min(ans, 
                I[lower_bound(I.begin(),I.end(),O[i+k-1])-I.begin()+k-1]-
                J[lower_bound(J.begin(),J.end(),O[i])-J.begin()-k]+1-3*k);
    cout << (ans==10*n ? -1 : ans) << '\n';
    return 0;
}

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