Submission #415316

#	Time	Username	Problem	Language	Result	Execution time	Memory
415316		Blagojce	Martian DNA (BOI18_dna)	C++11	100 / 100	43 ms	4500 KiB

dna

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;

mt19937 _rand(time(NULL));
const int mxn = 2e5;

int n, k, r;

int a[mxn];
int c[mxn];

int cnt[mxn];

void solve(){
	cin >> n >> k >> r;	
	fr(i, 0, n){
		cin >> a[i];
	}
	fr(i, 0, r){
		int nuc;
		cin >> nuc >> c[nuc];
	}
	int in = 0;
	int p = 0;
	while(in < r && p < n){
		cnt[a[p]] ++;
		if(cnt[a[p]] == c[a[p]]){
			++in;
		}
		++p;
	}
	if(in < r){
		cout<<"impossible"<<endl;
		return;
	}
	--p;
	
	int ans = p+1;
	
	int l = 0;
	
	while(p < n){
		while(l < p && cnt[a[l]] > c[a[l]]){
			cnt[a[l]]--;
			++l;
		}
		ans = min(ans, p-l+1);
		
		++p;
		if(p < n){
			cnt[a[p]]++;
		}
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}

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