제출 #1280435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280435		hanguyendanghuy	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	7 ms	5332 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=1e6+5,MAXV=3e5,MOD=1e9+7,INF=1e18;
ll n,m,i,j,p,k,ans,dem,pre[MAXN],suf[MAXN];
string s;
ll dist(ll st,ll en){
    return en-st+1-k;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k>>s;
    ll cntO=0,cntJ=0,cntI=0;
    queue<ll> O,I,J;
    pre[0]=suf[n+1]=-1;
    for(i=1;i<=n;i++){   
        if(s[i-1]=='J') J.push(i);
        while(J.size()>k) J.pop();
        if(J.size()==k)
            pre[i]=J.front();
        else pre[i]=-1;
    }
    for(i=n;i>=1;i--){
        if(s[i-1]=='I') I.push(i);
        while(I.size()>k) I.pop();
        if(I.size()==k) 
            suf[i]=I.front();
        else suf[i]=-1;
    }
    ll ans=INF;
    for(i=1;i<=n;i++){
        if(s[i-1]=='O') O.push(i);
        while(O.size()>k) O.pop();
        if(O.size()==k){
            ll st=O.front();
            if(suf[i+1]==-1||pre[st-1]==-1) continue;
            ll p=pre[st-1],s=suf[i+1];
            ans=min(ans,dist(p,st-1)+dist(st,i)+dist(i+1,s));
        }
    }
    if(ans==INF){
        cout<<-1;
        return 0;
    }
    cout<<ans;
}

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