Submission #1148786

#TimeUsernameProblemLanguageResultExecution timeMemory
1148786dostsJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
18 ms6880 KiB
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e5+1,MOD = 998244353,B = 250;

void solve() { 
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vi js(n+1,0),os(n+1,0),is(n+1,0);
    for (int i=1;i<=n;i++) {
        js[i] = js[i-1]+(s[i-1] == 'J');
        os[i] = os[i-1]+(s[i-1] == 'O');
        is[i] = is[i-1]+(s[i-1] == 'I');
    }
    int ans = inf;
    for (int i=1;i<=n;i++) {
        int p = i;
        int l = 1,r = n;
        while (l<=r) {
            int m = (l+r) >> 1;
            if (js[m]-js[p-1] < k) l = m+1;
            else r = m-1;
        }
        if (l > n) continue;
        p = l;
        l = p+1;
        r = n;
        while (l<=r) {
            int m = (l+r) >> 1;
            if (os[m]-os[p-1] < k) l = m+1;
            else r = m-1;
        }
        if (l > n) continue;
        p = l;
        l =  p+1;
        r = n;
        while (l <= r) {
            int m = (l+r) >> 1;
            if (is[m]-is[p-1] < k) l = m+1;
            else r = m-1;
        }
        if (l > n) continue;
        ans = min(ans,l-i+1-3*k);
    }
    if (ans < inf) cout << ans << '\n';
    else cout << -1 << '\n';
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...