Submission #1298906

#TimeUsernameProblemLanguageResultExecution timeMemory
1298906muhammad-ahmadJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
23 ms7936 KiB
// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

void solve() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	s = "." + s;
	int pref[n + 1] = {};
	vector<int> idxj, idxo, idxi;
	for (int i = 1; i <= n; i++){
		if (s[i] == 'J') idxj.push_back(i);
		if (s[i] == 'O') idxo.push_back(i);
		if (s[i] == 'I') idxi.push_back(i);
		pref[i] = pref[i - 1] + (s[i] == 'O');
	}	
	
	set<pair<int, int>> S;
	int m = idxi.size();
	for (int i = 0; i < m; i++){
		S.insert({pref[idxi[i]], i});
	} 
	
	int ans = 1e18;
	
	m = idxj.size();
	
	for (int i = k - 1; i < m; i++){
		auto it = S.lower_bound({pref[idxj[i]] + k, 0});
		if (it == S.end()) continue;
		auto [val, idx] = *it; 
		if (idx + k - 1 < (int) idxi.size()) ans = min(ans, idxi[idx + k - 1] - idxj[i - k + 1] + 1);
	}
	if (ans == 1e18) ans = 3 * k - 1;
	cout << ans - 3 * k << endl;
	
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
    return 0;
}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...