Submission #826694

#	Time	Username	Problem	Language	Result	Execution time	Memory
826694		serifefedartar	Martian DNA (BOI18_dna)	C++17	100 / 100	38 ms	4720 KiB

dna

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005

vector<pair<int,int>> req;
vector<int> DNA;
int main() {
	fast
	int N, K, R;
	cin >> N >> K >> R;

	vector<int> matching(N+1, -1);
	req = vector<pair<int,int>>(R);
	DNA = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> DNA[i];

	for (int i = 0; i < R; i++) {
		cin >> req[i].f >> req[i].s;
		matching[req[i].f] = i;
	}

	int l = 1, r = 1, no_of_closed = 0;
	if (matching[DNA[l]] != -1) {
		req[matching[DNA[l]]].s--;
		if (req[matching[DNA[l]]].s == 0)
			no_of_closed++;
	}

	int ans = INT_MAX;
	while (l <= N && r <= N) {
		while (no_of_closed < R && r < N) {
			r++;
			if (matching[DNA[r]] != -1) {
				req[matching[DNA[r]]].s--;
				if (req[matching[DNA[r]]].s == 0)
					no_of_closed++;
			}
		}

		if (no_of_closed == R)
			ans = min(r-l+1, ans);

		if (matching[DNA[l]] != -1) {
			req[matching[DNA[l]]].s++;
			if (req[matching[DNA[l]]].s == 1)
				no_of_closed--;
		}
		l++;
	}

	if (ans == INT_MAX)
		cout << "impossible\n";
	else
		cout << ans << "\n";
}

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