제출 #1191800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191800		bestbest	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	19 ms	3088 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define  en '\n'
#define  sp ' '
typedef long long ll;
#define Linux ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int,int>

const int N=2e5+10;
const ll M=1e9+7;
int n,k;
string s;
int sj[N],so[N],si[N];
int mi=M;
int sum;


int main(){Linux
    cin >> n >> k;
    cin >> s;
    s='0'+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='J')sj[i]++;
        else if(s[i]=='O')so[i]++;
        else si[i]++;
        sj[i]+=sj[i-1];
        so[i]+=so[i-1];
        si[i]+=si[i-1];
        // cout << sj[i] << ',' << so[i] << ',' << si[i] << sp;
    }
    sj[n+1]=sj[n];
    so[n+1]=so[n];
    si[n+1]=si[n];

    // cout << (lower_bound(sj,sj+n+1,3)-sj) << en;

    for(int i=1;i<=n;i++){
        // cout << i << sp;
        sum=0;
        int it1=lower_bound(sj,sj+n+1,sj[i-1]+k)-sj;
        if(it1<=n){
            sum+=it1-i+1-sj[it1]+sj[i-1];
            // cout << it1 << sp;
            int it2=lower_bound(so,so+n+1,so[it1]+k)-so;
            if(it2<=n){
                sum+=it2-it1-so[it2]+so[it1];
                // cout << it2 << sp;
                int it3=lower_bound(si,si+n+1,si[it2]+k)-si;
                if(it3<=n){
                    sum+=it3-it2-si[it3]+si[it2];
                    // cout << it3 << sp;
                }
                else continue;
            }
            else continue;
        }
        else continue;
        // cout << sum << en;
        mi=min(mi,sum);
    }
    if(mi==M)cout << -1 << en;
    else cout << mi << en;

    return 0;
}

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