제출 #1158340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158340		dnnnda	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	13 ms	3284 KiB

ho_t2

#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;
}

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