Submission #396650

#	Time	Username	Problem	Language	Result	Execution time	Memory
396650		miss_robot	Martian DNA (BOI18_dna)	C++14	100 / 100	42 ms	4548 KiB

dna

#include <bits/stdc++.h>

using namespace std;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n, k, r, a = 0, b = 0, d = 0, e = 1e6;
	cin >> n >> k >> r;
	vector<int> s(n), q(k), o(k);
	for(int &x : s) cin >> x;
	for(int i = 0; i < r; i++){
		int f, g;
		cin >> f >> g;
		q[f] = g;
	}
	o[s[0]] = 1;
	if(q[s[0]] == 1) d++;
	if(d == r) e = 1;
	for(;;){
		if(d == r){
			if(o[s[a]] == q[s[a]]) d--;
			o[s[a]]--;
			a++;
			if(d == r) e = min(e, b-a+1);
		}
		else{
			b++;
			if(b == n) break;
			o[s[b]]++;
			if(o[s[b]] == q[s[b]]) d++;
			if(d == r) e = min(e, b-a+1);
		}
	}
	if(e == 1e6) cout << "impossible\n";
	else cout << e << "\n";
}

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