제출 #1158340

#제출 시각아이디문제언어결과실행 시간메모리
1158340dnnndaJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
13 ms3284 KiB
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

int pre[3][200010], ans=inf;

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(pre,0,sizeof pre);
    int n, k; cin >> n >> k;
    string s; cin >> s;
    s="."+s;
    for(int i=1 ; i<=n ; i++){
        if(s[i]=='J') pre[0][i]++;
        else if(s[i]=='O') pre[1][i]++;
        else pre[2][i]++;
    }
    for(int i=0 ; i<3 ; i++) for(int j=1 ; j<=n ; j++) pre[i][j]+=pre[i][j-1];
    for(int i=0 ; i<3 ; i++) for(int j=n+1 ; j<=n+5 ; j++) pre[i][j]=inf;
    for(int i=1 ; i<=n ; i++){
        if(s[i]!='J') continue;
        int it=lower_bound(pre[0],pre[0]+n+5,pre[0][i-1]+k)-pre[0]+1;
        it=lower_bound(pre[1],pre[1]+n+5,pre[1][it-1]+k)-pre[1]+1;
        it=lower_bound(pre[2],pre[2]+n+5,pre[2][it-1]+k)-pre[2]+1;
        if(it<=n+1) ans=min(ans,it-i);
    }
    if(ans>=inf) cout << "-1\n";
    else cout << ans-3*k << '\n';


    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...