Submission #959870

#	Time	Username	Problem	Language	Result	Execution time	Memory
959870		Champ_Naman	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	26 ms	5864 KiB

ho_t2

#include<bits/stdc++.h>
#define int long long
#define nl endl
using namespace std;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);

    int n, k;
    cin>>n>>k;
    string s; cin>>s;
 
    vector<int> Jcnt(n), Ocnt(n), Icnt(n);
    Jcnt[0] = (s[0] == 'J'), Ocnt[0] = (s[0] == 'O'), Icnt[0] = (s[0] == 'I');
    for(int i=1; i<n; i++){
        Jcnt[i] = Jcnt[i-1] + (s[i] == 'J');
        Ocnt[i] = Ocnt[i-1] + (s[i] == 'O');
        Icnt[i] = Icnt[i-1] + (s[i] == 'I');
    }

    int ans = 1e18;
    for(int i=0; i<n; i++){
        int Jstart = lower_bound(Jcnt.begin(), Jcnt.end(), i+1) - Jcnt.begin();

        int Jend = lower_bound(Jcnt.begin(), Jcnt.end(), i + k) - Jcnt.begin();
        if(Jend >= n) continue;
        int Oend = lower_bound(Ocnt.begin(), Ocnt.end(), Ocnt[Jend] + k) - Ocnt.begin();
        if(Oend >= n) continue;
        int Iend = lower_bound(Icnt.begin(), Icnt.end(), Icnt[Oend] + k) - Icnt.begin();
        if(Iend >= n) continue;

        //if(Jend >= n or Oend >= n or Iend >= n) continue;

        ans = min(ans, (Iend - Jstart + 1) - (3*k));
    }
 
    if(ans == 1e18) cout<<-1;
    else cout<<ans;
    return 0;
}

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