Submission #1123742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123742		zentan	Martian DNA (BOI18_dna)	C++17	68 / 100	2088 ms	14440 KiB

dna

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

#define int long long

bool valid(map<int,int> &req, map<int,int> &current) {
	if(current.size() < req.size()) return false; 
	
	for(auto &[key, value] : req) {
		if(current[key] < value) return false; 
	}
	
	return true; 
}

signed main() {
	
	int N, K, R; 
	cin >> N >> K >> R; 
	
	vector<int> dna(N); 
	for(int i = 0; i < N; i++) {
		cin >> dna[i]; 
	}
	
	map<int, int> req; 
	for(int i = 0; i < R; i++) {
		int a, b; 
		cin >> a >> b; 
		req[a] = b; 
	}
	
	int ans = LLONG_MAX; 
	//sliding window
	map<int,int> current; 
	int l(0), r(0); //no elements selected
	while(r <= N) {
		if(!valid(req, current)) { //not valid
			// cout << "invalid: " << l << " " << r << "\n"; 
			current[dna[r]] += 1; 
			r++; 
		} 
		else { //valid
			// cout << "valid: " << l << " " << r << "\n"; 
			ans = min(ans, r-l); 
			current[dna[l]] -= 1; 
			l++; 
		}
	}
	
	if(ans == LLONG_MAX) {
		cout << "impossible\n"; 
	} else {
		cout << ans << "\n"; 
	}
	
	
	return 0; 
}

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