Submission #824787

#	Time	Username	Problem	Language	Result	Execution time	Memory
824787		ThylOne	Martian DNA (BOI18_dna)	C++14	100 / 100	75 ms	4508 KiB

dna

#include<bits/stdc++.h>

using namespace std;

int main(){
	int N,K,R;cin>>N>>K>>R;
	vector<int> nums(N);
	int occ[K];
	int wantedOcc[K];
	for(int i = 0 ; i <K;i++)occ[i]=wantedOcc[i]=0;
	for(int i = 0 ; i <N;i++){cin>>nums[i];}
	
	
	for(int i=0;i<R;i++){
		int nuc,w;cin>>nuc>>w;
		wantedOcc[nuc]=w;
	}
	int ans = N+1;
	int left=0;
	int nbGood=0;
	for(int p=0;p<N;p++){
		int val=nums[p];
		if(wantedOcc[val]==0)continue;
		occ[val]++;
		if(occ[val]==wantedOcc[val]){
			nbGood++;
		}
		while(nbGood==R && left<N && (wantedOcc[nums[left]]==0 || occ[nums[left]]-1>=wantedOcc[nums[left]])){
			int val2 = nums[left];
			occ[nums[left]]--;
			left++;
			if(wantedOcc[val2]==0)continue;
		}
		
		
		if(nbGood==R){
			ans = min(ans,p-left+1);
		}
	}
	if(ans==N+1){
		cout<<"impossible"<<endl;
	}else{
		cout<<ans<<endl;
	}
	
	
	return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32