Submission #330152

#	Time	Username	Problem	Language	Result	Execution time	Memory
330152		nandonathaniel	Martian DNA (BOI18_dna)	C++14	68 / 100	2098 ms	3948 KiB

dna

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

int mini[200005],skg[200005];
int s[200005];
vector<int> v;

bool check(){
	for(auto i : v){
		if(skg[i]<mini[i])return false;
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n,k,r,x,y;
    cin >> n >> k >> r;
    for(int i=0;i<n;i++)cin >> s[i];
    for(int i=1;i<=r;i++){
    	cin >> x >> y;
    	v.push_back(x);
    	mini[x]=y;
	}
	int ans=n+1;
    int awal=0,akhir=0;
    skg[s[0]]++;
    while(awal<=akhir && akhir<n){
    	bool stat=check();
    	if(!stat){
    		if(akhir<n-1){
    			akhir++;
    			skg[s[akhir]]++;
			}
			else break;
		}
		else{
			ans=min(ans,akhir-awal+1);
			skg[s[awal]]--;
			awal++;
		}
	}
	if(ans==n+1)cout << "impossible\n";
	else cout << ans << '\n';
	return 0;
}

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