oj.uz

Submission #748242

# Submission time Handle Problem Language Result Execution time Memory
748242 2023-05-25T20:38:51 Z JellyTheOctopus Martian DNA (BOI18_dna) C++17
0 / 100
 93 ms 2348 KB 
#include <bits/stdc++.h>
using namespace std;

int N, K, R;

int main() {
	cin >> N >> K >> R;
	vector<int> arr(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	vector<int> need(K, INT_MAX);
	for (int i = 0; i < R; i++) {
		int B, Q;
		cin >> B >> Q;
		need[B] = Q;
	}
	deque<int> d;
	vector<int> freq(K);
	int done = 0;
	int i = 0;
	int ans = INT_MAX;
	while (i < N) {
		while (done < R && i < N) {
			d.push_back(i);
			freq[arr[i]]++;
			if (freq[arr[i]] == need[arr[i]]) {
				done++;
			}
			i++;
		}
		while (done == R) {
			int j = d.front();
			d.pop_front();
			freq[arr[j]]--;
			ans = min(ans, i-j);
			if (freq[arr[j]] == need[arr[j]]-1) {
				done--;
				break;
			}
		}
		i++;
	}
	if (ans == INT_MAX) {
		cout << "impossible\n";
	}
	else {
		cout << ans << "\n";
	}
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 2348 KB Output isn't correct
2 Halted 0 ms 0 KB -