Submission #1123568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123568		jjjwong	Martian DNA (BOI18_dna)	C++20	100 / 100	32 ms	3012 KiB

dna

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

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int N, K, R;
	cin >> N >> K >> R;
	
	vector<int> A;
	int req[K], curr[K];
	int ans = 0;
	
	fill(req, req+K, 0);
	fill(curr, curr+K, 0);
	
	for (int i=0; i<N; ++i) {
		int n;
		cin >> n;
		A.emplace_back(n);
	}
	
	for (int i=0; i<R; ++i) {
		int n, amt;
		cin >> n >> amt;
		req[n] = amt;
	}
	
	int req_met = 0;
	
	if (R == 0) {
		cout << 1;
		return 0;
	}
	
	int l = 0, r = 0;
	
	while (l < N) {
		if (req_met < R && r<N) {
			curr[A[r]]++;
			if (req[A[r]] > 0 && curr[A[r]] == req[A[r]]) req_met++;
			r++; 
		}
		else {
			if (req_met >= R) {
				if (ans == 0) ans = r - l;
				else ans = min(ans, r-l);
			}
			curr[A[l]]--;
			if (req[A[l]] > 0 && curr[A[l]] < req[A[l]]) req_met--;
			l++;
		}
	}
	
	if (ans != 0) cout << ans;
	else cout << "impossible";
	
	return 0;
}

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