답안 #748244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748244	2023-05-25T20:41:26 Z	JellyTheOctopus	Martian DNA (BOI18_dna)	C++17	100 / 100	99 ms	5284 KB

dna

#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]]--;
			if (freq[arr[j]] == need[arr[j]]-1) {
				done--;
				ans = min(ans, i-j);
				break;
			}
		}
	}
	if (ans == INT_MAX) {
		cout << "impossible\n";
	}
	else {
		cout << ans << "\n";
	}
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	1 ms	312 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	300 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	304 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	1472 KB	Output is correct
2	Correct	29 ms	1588 KB	Output is correct
3	Correct	30 ms	1492 KB	Output is correct
4	Correct	29 ms	1712 KB	Output is correct
5	Correct	58 ms	3240 KB	Output is correct
6	Correct	27 ms	2240 KB	Output is correct
7	Correct	32 ms	2352 KB	Output is correct
8	Correct	61 ms	4516 KB	Output is correct
9	Correct	49 ms	2484 KB	Output is correct
10	Correct	29 ms	1720 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	2 ms	316 KB	Output is correct
14	Correct	3 ms	340 KB	Output is correct
15	Correct	2 ms	340 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	304 KB	Output is correct
18	Correct	1 ms	296 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	1976 KB	Output is correct
2	Correct	75 ms	3444 KB	Output is correct
3	Correct	63 ms	3108 KB	Output is correct
4	Correct	30 ms	1472 KB	Output is correct
5	Correct	95 ms	4772 KB	Output is correct
6	Correct	99 ms	5284 KB	Output is correct
7	Correct	52 ms	2864 KB	Output is correct
8	Correct	54 ms	3004 KB	Output is correct
9	Correct	26 ms	1864 KB	Output is correct
10	Correct	28 ms	1620 KB	Output is correct
11	Correct	31 ms	1460 KB	Output is correct
12	Correct	29 ms	1708 KB	Output is correct
13	Correct	55 ms	3128 KB	Output is correct
14	Correct	27 ms	2224 KB	Output is correct
15	Correct	33 ms	2380 KB	Output is correct
16	Correct	67 ms	4544 KB	Output is correct
17	Correct	50 ms	2468 KB	Output is correct
18	Correct	29 ms	1716 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	308 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	312 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	300 KB	Output is correct
26	Correct	0 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	0 ms	304 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	1 ms	300 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	212 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct