Submission #938135

#	Time	Username	Problem	Language	Result	Execution time	Memory
938135		freedommo33	Martian DNA (BOI18_dna)	C++17	100 / 100	26 ms	4160 KiB

dna

#include <bits/stdc++.h>

using namespace std;
constexpr int M = 200005;
int tab[M];
int wymagane[M];
bool czyPotrzeba[M];

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, k, ileL;
	cin>>n>>k>>ileL;
	for(int i=1; i<=n; i++) cin>>tab[i];
	for(int i=1; i<=ileL; i++){
		int a, b;
		cin>>a>>b;
		wymagane[a] = b;
		czyPotrzeba[a] = 1;
	}
	int l = 1;
	int ileJuz = 0;
	int wynik = M + 2;
	int dlugosc = 0;
	for(int r=1; r<=n; r++){
		while(l<=n && ileJuz < ileL){
			wymagane[ tab[l] ]--;
			if(wymagane[tab[l]] == 0 && czyPotrzeba[tab[l]]==1) ileJuz++;
			dlugosc++;
			if(ileJuz == ileL) wynik = min(wynik, dlugosc);
			l++;
		}
		wymagane[ tab[r] ]++;
		if(wymagane[tab[r]]==1 && czyPotrzeba[tab[r]]==1) ileJuz--;
		dlugosc--;
		if(ileJuz == ileL) wynik = min(wynik, dlugosc);
	}
	if(wynik==M+2) cout<<"impossible"<<endl;
	else cout<<wynik<<endl;
	return 0;
}

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