제출 #1123866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123866		fiips	Martian DNA (BOI18_dna)	C++20	0 / 100	35 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){
        while(1){
			    cnt[dna[l]]--;
			    if(cnt[dna[l]] < req[dna[l]]) {
                  s.erase(dna[l]); 
                  break;
			    }
			
			    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