Submission #217111

#	Time	Username	Problem	Language	Result	Execution time	Memory
217111		jamielim	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	43 ms	3192 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	char str[n+5];
	scanf("%s",str);
	int pre[3][n+1];
	for(int i=0;i<n;i++){
		if(i>0){pre[0][i]=pre[0][i-1];pre[1][i]=pre[1][i-1];pre[2][i]=pre[2][i-1];}else{pre[0][i]=pre[1][i]=pre[2][i]=0;}
		if(str[i]=='O'){
			pre[0][i]=(i==0?1:pre[0][i-1]+1);
		}else if(str[i]=='I'){
			pre[1][i]=(i==0?1:pre[1][i-1]+1);
		}else{
			pre[2][i]=(i==0?1:pre[2][i-1]+1);
		}
	}
	pre[0][n]=1000000010;pre[1][n]=1000000010;pre[2][n]=1000000010;
	int j=0;
	int ans=1000000010;
	for(int i=0;i<n;i++){
		if(str[i]=='J')j++;
		if(j>=k){
			int cur=0;
			int x=lower_bound(pre[2],pre[2]+n+1,j-k+1)-pre[2];
			cur+=i-x+1-k;
			x=lower_bound(pre[0],pre[0]+n+1,k+pre[0][i])-pre[0];
			if(x==n)continue;
			cur+=x-i-k;
			int y=lower_bound(pre[1],pre[1]+n+1,k+pre[1][x])-pre[1];
			if(y==n)continue;
			cur+=y-x-k;
			ans=min(cur,ans);
		}
	}
	if(ans>=1000000010)printf("-1");
	else printf("%d",ans);
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
ho_t2.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",str);
  ~~~~~^~~~~~~~~~

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