Submission #1124458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124458		henriess	Martian DNA (BOI18_dna)	C++20	100 / 100	311 ms	19364 KiB

dna

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n,k,r;cin >> n >> k >> r;
	vector<long long> v(n);
	set<long long> s;
	map<long long,long long> m;
	for(int i = 0;i<n;i++){
		cin >> v[i];
	}
	for(int i = 0;i<r;i++){
		long long gene,required;
		cin >> gene >> required;
		m[gene] = required;
	}
	long long left = 0;
	long long current = 0;
	long long ans = LLONG_MAX;
	long long completed = 0;
	map<long long, long long> track;
	for(int i = 0;i<n;i++){
		if (track[v[i]] == 0){
			track[v[i]] = 1;
		}
		else{
			track[v[i]] += 1;
		}
		if (m.find(v[i]) != m.end() && track[v[i]] == m[v[i]]){
			completed += 1;

		}
		while (completed >= r){
			ans = min(ans,i - left+ 1);
			track[v[left]]--;
			if (m.find(v[left]) != m.end() && track[v[left]] == m[v[left]]-1){
				completed--;
			}
			left++;
		}
	}
	if (ans == LLONG_MAX){
		cout << "impossible";
		return 0;
	}
	cout << ans;
}
	

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