제출 #1341895

#제출 시각아이디문제언어결과실행 시간메모리
1341895iq500JJOOII 2 (JOI20_ho_t2)C++20
100 / 100
14 ms4620 KiB
//supernova - yunosuke & haruno
#include <bits/stdc++.h>
#define pb push_back
#define fir first
#define sec second
#define int long long
using namespace std;

signed main(){

    int n, k; cin>>n>>k;
    string s; cin>>s;
    vector<int> vj, vo, vi;
    vector<int> dj(1, 0), di(1, 0);
    for(int i=0; i<n; i++){
        if(s[i]=='J') vj.pb(i);
        else if(s[i]=='O') vo.pb(i);
        else vi.pb(i);
    }
    if(vo.size()<k || vj.size()<k || vi.size()<k){
        cout<<-1;
        return 0;
    }

    for(int i=0; i<vj.size()-1; i++){
        dj.pb(vj[i+1]-vj[i]-1);
    }
    for(int i=0; i<vi.size()-1; i++){
        di.pb(vi[i+1]-vi[i]-1);
    }

    vector<int> pj(dj.size(), 0);
    vector<int> pi(di.size(), 0);

    for(int i=1; i<dj.size(); i++){
        pj[i]=pj[i-1]+dj[i];
    }
    for(int i=1; i<di.size(); i++){
        pi[i]=pi[i-1]+di[i];
    }

    int ort=0;
    for(int i=0; i<k-1; i++){
        ort+=vo[i+1]-vo[i]-1;
    }

    int ans=LLONG_MAX;

    for(int i=0; i<=vo.size()-k; i++){
        int tmp=ort;
        int son=i+k-1;

        //sonda o'lar 1 kayıyor
        if(i+1<vo.size()){
            ort-=vo[i+1]-vo[i]-1;
        }
        if(son+1<vo.size()){
            ort+=vo[son+1]-vo[son]-1;
        }


        auto sol=lower_bound(vj.begin(), vj.end(), vo[i]);
        int r1=sol-vj.begin()-1;
        int l1=r1-k+1;
        if(l1<0){
            continue;
        }
        tmp+=vo[i]-vj[r1]-1; //sağdaki j ve soldaki o arası
        tmp+=pj[r1]-pj[l1];

        auto sag=lower_bound(vi.begin(), vi.end(), vo[son]);
        int l2=sag-vi.begin();
        int r2=l2+k-1;
        if(r2>=vi.size()) continue;
        tmp+=vi[l2]-vo[son]-1;
        tmp+=pi[r2]-pi[l2];

        ans=min(ans, tmp);
    }
    if(ans==LLONG_MAX) cout<<-1;
    else cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...