Submission #212142

#	Time	Username	Problem	Language	Result	Execution time	Memory
212142		kshitij_sodani	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	38 ms	9984 KiB

ho_t2

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,k;
	cin>>n>>k;
	char ss;
	int it[n];
	for(int i=0;i<n;i++){
		cin>>ss;
		if(ss=='O'){
			it[i]=1;
		}
		else if(ss=='I'){
			it[i]=2;
		}
		else{
			it[i]=0;
		}
	}
	int pre[n];
	pre[0]=0;
	if(it[0]==1){
		pre[0]=1;
	}
	for(int i=1;i<n;i++){
		pre[i]=pre[i-1];
		pre[i]+=it[i]%2;
	}
	multiset<int> aa;
	multiset<int,greater<int>> bb;
	int dp[n];
	int dp2[n];
	for(int i=0;i<n;i++){
		dp[i]=n+1;
		dp2[i]=n+1;
	}

	for(int i=0;i<n;i++){
		if(it[i]==0){
			aa.insert(i);
			if(aa.size()>k){
				auto ac=aa.begin();
				aa.erase(ac);
			}
			if(aa.size()==k){
				dp[i]=(i-(*aa.begin())+1-k);
			}
		}
		if(i>0){
			dp[i]=min(dp[i],dp[i-1]+1);
		}
	}

	for(int i=n-1;i>=0;i--){
		if(it[i]==2){
			bb.insert(i);
			if(bb.size()>k){
				auto ac=bb.begin();
				bb.erase(ac);
			}
			if(bb.size()==k){
				dp2[i]=((*bb.begin())-i+1-k);
			}
		}
		if(i<n-1){
			dp2[i]=min(dp2[i],dp2[i+1]+1);
		}
	}
	int mi=n+1;
	int ind=0;	
	int ans=n+1;
	/*for(int i=0;i<n;i++){
		cout<<dp[i]<<" ";
	}
	cout<<endl;*/
/*	muliset<int> ak;
	multiset<int> bk;
*/
	for(int i=2;i<n;i++){
		mi+=1;
		while(ind<i-1){
			if(pre[i-1]-pre[ind]>=k){
				mi=min(mi,dp[ind]+(i-1-ind-k));
				ind+=1;
			}
			else{
				break;
			}

		}
		
		ans=min(ans,mi+dp2[i]);
	}	
	if(ans<=n){
		cout<<ans<<endl;
	}
	else{
		cout<<-1<<endl;
	}




	



























	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(aa.size()>k){
       ~~~~~~~~~^~
ho_t2.cpp:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(aa.size()==k){
       ~~~~~~~~~^~~
ho_t2.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(bb.size()>k){
       ~~~~~~~~~^~
ho_t2.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(bb.size()==k){
       ~~~~~~~~~^~~

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