Submission #1198366

#TimeUsernameProblemLanguageResultExecution timeMemory
1198366TahirAliyevJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
5 ms3596 KiB
#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #define int long long
#define ld long double
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 1e5 + 5, LOGMAX = 20, B = 441, MOD = 998244353;

void solve(){
    int n, k; cin >> n >> k;
    string s; cin >> s;
    s = "S" + s;
    queue<int> q[3];
    map<char, int> mp = {{'J', 0}, {'O', 1}, {'I', 2}};
    int nxt[n + 1][3];
    memset(nxt, 0, sizeof(nxt));
    int ans = oo;
    for(int i = 1; i <= n; i++){
        q[mp[s[i]]].push(i);
        for(int j = 0; j < 3; j++){
            if(q[j].size() > k) q[j].pop();
            if(q[j].size() == k) nxt[i][j] = q[j].front();
        }
        int j = nxt[nxt[nxt[i][2]][1]][0];
        if(j != 0) ans = min(ans, (i - j + 1) - 3 * k);
    }
    if(ans == oo) ans = -1;
    cout << ans << '\n';
}   

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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...