Submission #931324

#	Time	Username	Problem	Language	Result	Execution time	Memory
931324		armashka	Martian DNA (BOI18_dna)	C++17	100 / 100	28 ms	4924 KiB

dna

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5 + 5;
const ll inf = 1e18;

int n, k, R;
int a[N], need[N];
int cnt[N], done, ans = 1e9;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> k >> R;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int i = 1; i <= R; ++ i) {
		int x, y;
		cin >> x >> y;
		need[x] = y;
	}

	int l = 1, r = 0;
	while (r < n) {
		++ r;
		++ cnt[a[r]];
		if (cnt[a[r]] == need[a[r]]) ++ done;

		while (l <= r && done == R) {
			ans = min(ans, r - l + 1);
			
			if (cnt[a[l]] == need[a[l]]) -- done;
			-- cnt[a[l]];
			++ l;
		}
	}
	if (ans == 1e9) cout << "impossible";
	else cout << ans;
}

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