Submission #1322227

#TimeUsernameProblemLanguageResultExecution timeMemory
1322227jumpJJOOII 2 (JOI20_ho_t2)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
#define int long long
int n,k;
std::vector<int> Jidx;
std::vector<int> Oidx;
std::vector<int> Iidx;
signed main() {
    std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
	std::cin >> n >> k;
	std::string str;
	std::cin >> str;
	for(int i=0;i<n;i++){
		if(str[i]=='J')Jidx.push_back(i);
		if(str[i]=='O')Oidx.push_back(i);
		if(str[i]=='I')Iidx.push_back(i);
	}
	int best = 1e18;
	for(int i=0;i<=Jidx.size()-k;i++){
		//std::cout << Jidx[i+k-1] << ' ' << Jidx[i] << '\n';
		int cost = Jidx[i+k-1]-Jidx[i]+1-k;
		int Os = std::upper_bound(Oidx.begin(),Oidx.end(),Jidx[i+k-1])-Oidx.begin();
		if(Os==Oidx.size())continue;
		cost+=Oidx[Os+k-1]-Oidx[Os]+1-k;
		int Is = std::upper_bound(Iidx.begin(),Iidx.end(),Oidx[Os+k-1])-Iidx.begin();
		if(Is==Iidx.size())continue;
		cost+=Iidx[Is+k-1]-Iidx[Is]+1-k;
		best=std::min(best,cost);
	}
	if(best==1e18)best=-1;
	std::cout << best << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...