Submission #1123841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123841		fiips	Martian DNA (BOI18_dna)	C++20	0 / 100	42 ms	6228 KiB

dna

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

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, k, ri;
	cin >> n >> k >> ri;
	
	int dna[n];
	for(int i = 0; i < n; i++) cin >> dna[i];
	
	int req[k];
	for(int i = 0; i < k; i++) req[i] = LLONG_MAX / 20; 
	
	for(int i = 0; i < ri; i++) {
		int a, b;
		cin >> a >> b;
		req[a] = b;
	}
	
	int cnt[k];
	memset(cnt, 0, sizeof(cnt));
	
	unordered_set<int> s;
	
	int ans = LLONG_MAX / 20, l = 0;
	for(int r = 0; r < n; r++) {
		cnt[dna[r]]++;
		if(cnt[dna[r]] >= req[dna[r]]) s.emplace(dna[r]);
		
		if(s.size() == ri) {
			cnt[dna[l]]--;
			if(cnt[dna[l]] < req[dna[l]]) s.erase(dna[l]); 
			
			ans = min(r - l + 1, ans); 
			l++;
		}
	}
	
	if(ans == LLONG_MAX / 20) cout << "impossible";
	else cout << ans;
}

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