Submission #1167580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167580		Petrix	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	8 ms	3032 KiB

ho_t2

#include <iostream>
#include <vector>
using namespace std;

string s;
int n,k;
vector<int> a,b,c;

vector<int> calc(char c){
	vector<int> a(n+2);
	int j=0,j1=0,i;
	for(i=0;i<n;i++){
		if(i && s[i-1]==c) j1--;
		while(j<n && j1<k){
			if(s[j]==c) j1++;
			j++;
		}
		if(j1==k) a[i]=j;
		else a[i]=n+1;
	}
	a[n]=a[n+1]=n+1;
	return a;
}

int main(){
    int rasp,i;
	cin>>n>>k>>s;rasp=n;
    a=calc('J');b=calc('O');c=calc('I');
	for(i=0;i<n;i++){
		if(c[b[a[i]]]<=n) rasp=min(rasp,c[b[a[i]]]-i-3*k);
	}
	if(rasp==n) cout<<"-1";
	else cout<<rasp;
}

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