Submission #1123826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123826		ilikeeggs	Martian DNA (BOI18_dna)	C++20	100 / 100	85 ms	5056 KiB

dna

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

int32_t main(){    
	int n,k,r; cin>>n>>k>>r;
	vector<int> dna(n);
	for (int i = 0; i < n; i++)
	{
		cin>>dna[i];
	}
	vector<int> req(n, 0);
	for (int i = 0; i < r; i++)
	{
		int b,q; cin>>b>>q;
		req[b] = q;
	}
	vector<int> cnt(n, 0);
	int L=0,R=0;
	int valid = 0;
	int ans = LLONG_MAX;
	pair<int,int> ref;
	while(R < n){
		cnt[dna[R]]++;
		if(cnt[dna[R]] == req[dna[R]] && req[dna[R]] != 0){
			valid++;
		}
		if(valid == r){
			ans = min(ans, R-L+1);
			ref = {L, R};
		}
		while(valid == r){
			cnt[dna[L]]--;
			if(cnt[dna[L]] == req[dna[L]]-1  && req[dna[L]] != 0){
				valid--;
			}
			L++;
			if(valid == r){
				ans = min(ans, R-L+1);
				ref = {L, R};
			}
		}
		R++;
	}
	if(ans == LLONG_MAX){
		cout << "impossible";
		return 0;
	}
	else{
		cout << ans << endl;
	}
}                                                                                                                                                     

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