제출 #1324283

#제출 시각아이디문제언어결과실행 시간메모리
1324283ivan_alexeevJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
26 ms3096 KiB
#include <bits/stdc++.h>

using namespace std;

#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif

using ll = long long;
const ll inf = 1'000'000'000;

int n, k;
vector<int> J, O, I;

int get(int l, int r, vector<int> &a){
    return a[r] - a[l];
}

int getr(int ind, vector<int> &a){
    int l = 0, r = n - ind + 1;
    while(l + 1 != r){
        int m = (l + r) / 2;
        if(get(ind, ind + m, a) >= k){
            r = m;
        }else{
            l = m;
        }
    }
    return r;
}

void solve(){
    cin >> n >> k;
    string s;
    cin >> s;
    J.resize(n + 1);
    O.resize(n + 1);
    I.resize(n + 1);
    for(int i = 0; i < n; i++){
        J[i + 1] = J[i] + (s[i] == 'J');
        O[i + 1] = O[i] + (s[i] == 'O');
        I[i + 1] = I[i] + (s[i] == 'I');
    } 
    int ans = inf;
    for(int i = 0; i < n; i++){
        int i2 = i + getr(i, J);
        if(i2 == n + 1){
            continue;
        }
        int i3 = i2 + getr(i2, O);
        if(i3 == n + 1){
            continue;
        }
        int i4 = i3 + getr(i3, I);
        if(i4 == n + 1){
            continue;
        }
        ans = min(ans, i4 - i - 3 * k);
    }
    if(ans != inf){
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...