제출 #1124450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124450		henriess	Martian DNA (BOI18_dna)	C++20	0 / 100	252 ms	11944 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 (track[v[i]] >= m[v[i]] && m.find(v[i]) != m.end() ){
			completed += 1;
		}
		while (completed >= r){
			ans = min(ans,i - left+ 1);
			track[v[left]]--;
			if (track[v[left]] <m[v[left]] && m.find(v[left]) != m.end()){
				completed--;
			}
			left++;
		}
	}
	if (ans == LLONG_MAX){
		cout << "impossible";
		return 0;
	}
	cout << ans;
}

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