Submission #1150789

#TimeUsernameProblemLanguageResultExecution timeMemory
1150789henriessJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
5 ms3016 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,k;cin >>n >> k;
    string s;cin >> s;
    //it's best to remove items at the ends 

    
	// Do a Sliding window 
	long long ans = LLONG_MAX;
	
	vector<long long> J;
	vector<long long> O;
	vector<long long> I;
	
	for(int i = 0;i<n;i++){
		if (s[i] == 'J'){
			J.push_back(i);
		}
		if(s[i] == 'O'){
			O.push_back(i);
		}
		if(s[i] == 'I'){
			I.push_back(i);
		}
	}
	
	long long Jpointer = 0;
	long long Opointer = 0;
	long long Ipointer = 0;
	//Note that only the Opointer and Ipointer need to move
	map<char,long long> m;
	long long index = 0;
	
	
	for(int i = 0;i<J.size();i++){
		Jpointer = J[i];
		if (i + k - 1 >= J.size()){
			break;
		}
		long long Jendpointer = J[i+k-1];
		
		while (Opointer < O.size() && O[Opointer] <= Jendpointer){
			Opointer += 1;
		}
		if (Opointer + k - 1 >= O.size()){
			continue;
		}
		long long Oendpointer = O[Opointer+k-1];
		while (Ipointer < I.size() && I[Ipointer] <= Oendpointer){
			Ipointer += 1;
		}
		if (Ipointer + k - 1 >= I.size()){
			continue;
		}
			
		ans = min(ans, I[Ipointer+k-1] - J[i] - 3*k + 1);
			
		

	}
	if (ans == LLONG_MAX){
		cout << -1;
		return 0;
	}
	cout << ans;
}
	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...