Submission #1190821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190821		Abdalaziz_Alshami	Martian DNA (BOI18_dna)	C++20	100 / 100	21 ms	3400 KiB

dna

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],n,k,R,t[N],h[N];
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>k>>R; 
	for(int i=0;i<n;i++) cin>>a[i];
	int sum=0;
	while(R--){
		int u,v; cin>>u>>v;;
		t[u]=v; sum+=v;
	}
	int ans=1e18;
	for(int i=0,j=0;i<n;i++){
		t[a[i]]--; 
		if(t[a[i]]>=0) sum--;
		while(t[a[j]]<0){
			t[a[j]]++; j++;
		}
		if(sum==0) ans=min(ans,i-j+1);
	}
	if(ans==1e18) cout<<"impossible";
	else cout<<ans;
}

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