Submission #1123736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123736		zentan	Martian DNA (BOI18_dna)	C++17	0 / 100	2094 ms	8468 KiB

dna

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

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; 
}

int 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 = INT_MAX; 
	//sliding window
	map<int,int> current; 
	int l(0), r(0); //no elements selected
	while(l<=r && r < N) {
		// cout << l << " " << r << "\n"; 
		if(!valid(req, current)) { //not valid
			current[dna[r]] += 1; 
			r++; 
		} 
		else {
			ans = min(ans, r-l); 
			current[dna[l]] -= 1; 
			l++; 
		}
	}
	
	if(ans == INT_MAX) {
		cout << "impossible\n"; 
	} else {
		cout << ans << "\n"; 
	}
	
	
	return 0; 
}

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