Submission #314011

#	Time	Username	Problem	Language	Result	Execution time	Memory
314011		Temmie	Martian DNA (BOI18_dna)	C++17	100 / 100	39 ms	4864 KiB

dna

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	int n, k, m; std::cin >> n >> k >> m;
	std::vector <int> a(n);
	for (int& x : a) std::cin >> x;
	std::vector <int> req(n, 0), has(n, 0);
	int cntgood = n;
	for (int i = 0; i < m; i++) {
		int t, h; std::cin >> t >> h;
		req[t] = h;
		cntgood--;
	}
	int ans = 1 << 30;
	for (int l = 0, r = 0; r < n; r++) {
		has[a[r]]++;
		if (has[a[r]] == req[a[r]]) cntgood++;
		while (cntgood == n && has[a[l]] > req[a[l]]) has[a[l++]]--;
		if (cntgood == n) ans = std::min(ans, r - l + 1);
	}
	if (ans == 1 << 30) std::cout << "impossible\n";
	else std::cout << ans << "\n";
	std::cout.flush();
	std::cin >> n;
	
}

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