Submission #312586

#	Time	Username	Problem	Language	Result	Execution time	Memory
312586		sofapuden	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	21 ms	3952 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n, k; string s; cin >> n >> k >> s;
	vector<int> J, O, 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);
	}
	if((int)J.size() < k){cout << -1 << "\n"; return 0;}
	if((int)O.size() < k){cout << -1 << "\n"; return 0;}
	if((int)I.size() < k){cout << -1 << "\n"; return 0;}
	vector<pair<int,int>> J2, O2, I2;
	for(int i = 0; i <= (int)J.size()-k; ++i)J2.push_back({J[i],J[i+k-1]});
	for(int i = 0; i <= (int)O.size()-k; ++i)O2.push_back({O[i],O[i+k-1]});
	for(int i = 0; i <= (int)I.size()-k; ++i)I2.push_back({I[i],I[i+k-1]});
	int p1 = 0, p2 = -1, p3 = 0;
	int ans = 2000000;
	while(p2 < (int)O2.size()-1){
		p2++;
		if(J2[p1].second > O2[p2].first)continue;
		while(J2[p1].second < O2[p2].first && p1 < (int)J2.size()-1){
			p1++;
		}
		if(J2[p1].second > O2[p2].first)p1--;
		while(O2[p2].second > I2[p3].first && p3 < (int)I2.size()-1){
			p3++;
		}
		if(O2[p2].second > I2[p3].first)break;
		ans = min(ans, I2[p3].second-J2[p1].first);
	}
	cout << (ans == 2000000 ? -1 : ans-3*k+1) << "\n";
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87