Submission #1188023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188023		kl0989e	Martian DNA (BOI18_dna)	C++20	100 / 100	21 ms	3400 KiB

dna

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

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k,r;
	cin >> n >> k >> r;
	vi a(n);
	vi cnt(k,0);
	for (int i=0; i<n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	vi need(k,0);
	int b,c;
	for (int i=0; i<r; i++) {
		cin >> b >> c;
		need[b]=c;
	}
	vi cur(k,0);
	int mn=1e9;
	int ok=count(all(need),0);
	r=0;
	for (int l=0; l<n; l++) {
		while (r<n && ok<k) {
			cur[a[r]]++;
			if (cur[a[r]]==need[a[r]]) {
				ok++;
			}
			r++;
		}
		if (ok==k) {
			mn=min(mn,r-l);
		}
		if (cur[a[l]]==need[a[l]]) {
			ok--;
		}
		cur[a[l]]--;
	}
	if (mn==1e9) {
		cout << "impossible\n";
	}
	else {
		cout << mn << '\n';
	}
	return 0;
}

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