제출 #964059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964059		Akshat369	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	17 ms	5924 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define endl '\n'
const int N = (int)1e5+5;


void Solve(){
    int n , k; cin>>n>>k;
    string s; cin>>s;
    deque<char> st;
    for(auto &i : s){
        st.push_back(i);
    }
    while (!st.empty() and st.front()!='J'){
        st.pop_front();
    }
    while(!st.empty() and st.back() != 'I'){
        st.pop_back();
    }
    if(st.empty()){
        cout<<-1<<endl;
        return;
    }
    s = " " + s;
    vi prej(n+1) , prei(n+1) , preo(n+1);

    for(int i = 1 ; i <= n ; i++){
        prej[i] = prej[i-1] + (s[i]=='J');
        prei[i] = prei[i-1] + (s[i]=='I');
        preo[i] = preo[i-1] + (s[i]=='O');
    }
//    cout<<"j"<<" ";
//    for(int i = 1 ; i<= n ; i++){
//        cout<<prej[i]<<" ";
//    }
//    cout<<endl;
//    cout<<"o"<<" ";
//    for(int i = 1 ; i<= n ; i++){
//        cout<<preo[i]<<" ";
//    }
//    cout<<endl;
//    cout<<"i"<<" ";
//    for(int i = 1 ; i<= n ; i++){
//        cout<<prei[i]<<" ";
//    }
//    cout<<endl;
    int ans = 1e18;
    for (int i = 1; i <= n; ++i) {
        if (s[i]=='J'){
            int j = lower_bound(prej.begin(), prej.end(),prej[i-1]+k) - prej.begin();
           // cout<<i<<" "<<j<<" " << preo[j]+k <<endl;
            if (j>=n+1)continue;
            int o = lower_bound(preo.begin(), preo.end(),preo[j]+k) - preo.begin();
          //  cout<<j<<" "<<o<<endl;
            if(o>=n+1) continue;
            int ii = lower_bound(prei.begin(), prei.end(),prei[o]+k) - prei.begin();
            if(ii>=n+1) continue;
            int temp = (ii-i+1 - (3*k));
           // cout<<temp<<endl;
            ans = min(ans,temp);
        }
    }
    if(ans>=1e18){
        cout<<-1<<endl;
        return;
    }
    cout<<ans<<endl;
}

int32_t main(){

    Solve();
}

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