This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;
using ll = long long;
void solve(){
ll n, k;
string s;
cin >> n >> k;
cin >> s;
// Use while loop and do dp
vector<ll> Os(n + 1, 0);
vector<ll> Js(n + 1, 0);
vector<ll> Is(n + 1, 0);
for(ll i = 0; i < n; i++){
Os[i + 1] = Os[i];
Js[i + 1] = Js[i];
Is[i + 1] = Is[i];
if(s[i] == 'O'){
Os[i + 1]++;
}else if(s[i] == 'J'){
Js[i + 1]++;
}else{
Is[i + 1]++;
}
}
ll Curr_min = 1E9;
for(ll i = 0; i < n; i++){
ll temp = 0;
if(Js[i + 1] < k){
continue;
}
ll l = 0;
ll r = i + 1;
while(l + 1 < r){
ll mid = (l + r)/2;
if(Js[i + 1] - Js[mid] >= k){
l = mid;
}else{
r = mid;
}
}
temp += i - l + 1 - k;
//cout << temp << endl;
ll new_start = -1;
l = i;
r = n;
while(l + 1 < r){
ll mid = (l + r)/2;
if(Os[mid] - Os[i] >= k){
r = mid;
}else{
l = mid;
}
}
temp += r - i - 1 - k;
//cout << temp << endl;
new_start = r;
if(Is[n] - Is[new_start] < k){
continue;
}
l = new_start;
r = n;
while(l + 1 < r){
ll mid = (l + r)/2;
if(Is[mid] - Os[new_start] >= k){
r = mid;
}else{
l = mid;
}
}
temp += r - new_start - k - 1;
Curr_min = min(Curr_min, max(temp, 0LL));
}
if(Curr_min == 1E9){
cout << -1;
}else{
cout << Curr_min;
}
}
int main(){
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
ll t = 1;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |