# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
771968 | Trisanu_Das | JJOOII 2 (JOI20_ho_t2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
using namespace std;
//limit definitions
#define N 200050
int n, k;
char s[202020];
int js[202020], os[202020], is[202020];
signed main() {
cin >> n >> k >> s;
for(int i = 1; i <= n; ++i) {
js[i] = js[i-1], os[i] = os[i - 1], is[i] = is[i - 1];
if(s[i] == 'J') ++js[i];
if(s[i] == 'O') ++os[i];
if(s[i] == 'I') ++is[i];
}
int ans = -1;
for(int i = 0; i < N; ++i) {
int np = i;
int jp = lower_bound(js+np, js+N+1, js[np]+K) - js;
if(jp == N+1) break;
int op = lower_bound(os+jp, os+N+1, os[jp]+K) - os;
if(op == N+1) break;
int ip = lower_bound(is+op, is+N+1, is[op]+K) - is;
if(ip == N+1) break;
if(ans == -1) ans = ip-np-3*K;
else ans = min(ans, ip-np-3*K);
}
cout << ans << '\n';
}