Submission #748242

#	Time	Username	Problem	Language	Result	Execution time	Memory
748242		JellyTheOctopus	Martian DNA (BOI18_dna)	C++17	0 / 100	93 ms	2348 KiB

dna

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

int N, K, R;

int main() {
	cin >> N >> K >> R;
	vector<int> arr(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	vector<int> need(K, INT_MAX);
	for (int i = 0; i < R; i++) {
		int B, Q;
		cin >> B >> Q;
		need[B] = Q;
	}
	deque<int> d;
	vector<int> freq(K);
	int done = 0;
	int i = 0;
	int ans = INT_MAX;
	while (i < N) {
		while (done < R && i < N) {
			d.push_back(i);
			freq[arr[i]]++;
			if (freq[arr[i]] == need[arr[i]]) {
				done++;
			}
			i++;
		}
		while (done == R) {
			int j = d.front();
			d.pop_front();
			freq[arr[j]]--;
			ans = min(ans, i-j);
			if (freq[arr[j]] == need[arr[j]]-1) {
				done--;
				break;
			}
		}
		i++;
	}
	if (ans == INT_MAX) {
		cout << "impossible\n";
	}
	else {
		cout << ans << "\n";
	}
}

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