Submission #382525

#	Time	Username	Problem	Language	Result	Execution time	Memory
382525		ritul_kr_singh	Martian DNA (BOI18_dna)	C++17	100 / 100	39 ms	3436 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, k, r; cin >> n >> k >> r;
	int a[n], b[k];
	fill(b, b+k, -n);
	for(int i=0; i<n; ++i) cin >> a[i];
	for(int i=0, j; i<r; ++i) cin >> j >> b[j];

	int i = 0, curr = n-r, ans = 1e18;
	for(int j=0; j<n; ++j){
		curr += --b[a[j]]==0;
		while(i<j and b[a[i]] < 0) ++b[a[i++]];
		if(curr==n) ans = min(ans, j-i+1);
	}
	if(ans==(int)1e18) cout << "impossible";
	else cout << ans;
}

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