Submission #1123745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123745		sigmaohiogyattrip	Martian DNA (BOI18_dna)	C++17	68 / 100	2094 ms	6216 KiB

dna

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

#define ll long long
#define ull unsigned long long
#define pll pair<ll,ll>
#define qll queue<ll>
#define inf LLONG_MAX
#define test return 12;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,k,r;cin>>n>>k>>r;
	ll c[n]; qll q;
	for(ll i=0;i<n;i++) {
		c[i];cin>>c[i];
	}
	ll cnt[k],req[k]; fill(req,req+k,0); fill(cnt,cnt+k,0); ll awa[r];
	for(ll i=0;i<r;i++) {
		ll a,b;cin>>a>>b;
		req[a]=b;
		awa[i]=a;
	}
	long long mean = LLONG_MAX;
	for(ll i=0;i<n;i++){
		q.push(c[i]);
		cnt[c[i]]++;
		bool flag=false;
		for(auto j:awa){
			if(cnt[j]<req[j])flag=true;
		}
		if(!flag){
			while(cnt[q.front()]-1>=req[q.front()]){
				cnt[q.front()]--;
				q.pop();
			}
		}
		if(!flag && q.size()<mean){
			mean=q.size();
		}
	}
	if (mean==inf){
		cout<<"impossible";
		return 0;
	}
	cout<<mean;
}
		

	

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