Submission #862797

#	Time	Username	Problem	Language	Result	Execution time	Memory
862797		maks007	Martian DNA (BOI18_dna)	C++14	100 / 100	666 ms	4660 KiB

dna

#include "bits/stdc++.h"

using namespace std;

signed main () {
	int n, k, q;
	cin >> n >> k >> q;
	vector <int> a(n);
	for(int i = 0; i < n; i ++) cin >> a[i];
	int cnt[k];
	memset(cnt, 0, sizeof(cnt));
	while(q --) {
		int val, sz;
		cin >> val >> sz;
		cnt[val] += sz;
	}
	int mn = 1e9, pref[k];
	memset(pref, 0, sizeof(pref));
	int l = 0, r = 0;
	for(;r<n;r++){
		pref[a[r]] ++;
		for(int j = 0; j < k; j ++) {
			if(cnt[j] <= pref[j]) continue;
			goto end;
		}
		break;
		end:;
	}
	if(r == n) {
		cout << "impossible";
		return 0;
	}
	mn = r-l+1;
	for(;r < n;) {
		while(1) {
			if(l == n) {
				break;
				// goto end2;
			}
			pref[a[l]] --;
			// cout << pref[a[l]] << " ";
			if(pref[a[l]] < cnt[a[l]]) {
				pref[a[l]] ++;
				// l--;
				break;
			}
			l ++;
		}
		// cout << l << " " << r << "\n";
		mn = min(mn, r-l+1);
		r++;
		if(r == n) break;
		pref[a[r]] ++;
	}
	cout << mn;
 	return 0;
}

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