Submission #975207

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
975207	2024-05-04T14:49:16 Z	Nipphitch	Martian DNA (BOI18_dna)	C++14	100 / 100	25 ms	4828 KB

dna

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;

int n,k,r,a[N],cnt[N],ans,mn[N],p=1;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k >> r;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=0;i<r;i++){
		int x,y;
		cin >> x >> y;
		mn[x]=y;
	}
	for(int i=0;i<k;i++) while(cnt[i]<mn[i] && p<=n) cnt[a[p++]]++;
	for(int i=0;i<k;i++){
		if(cnt[i]<mn[i]){
			cout << "impossible";
			return 0;
		}
	}
	ans=p-1;
	for(int i=1;i<=n;i++){
		cnt[a[i]]--;
		while(cnt[a[i]]<mn[a[i]] && p<=n) cnt[a[p++]]++;
		if(cnt[a[i]]<mn[a[i]]) break;
		ans=min(ans,p-i-1);
	}
	cout << ans;
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2508 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2512 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2520 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2508 KB	Output is correct
8	Correct	1 ms	2508 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2512 KB	Output is correct
11	Correct	1 ms	2512 KB	Output is correct
12	Correct	1 ms	2512 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	2396 KB	Output is correct
2	Correct	9 ms	2776 KB	Output is correct
3	Correct	10 ms	2904 KB	Output is correct
4	Correct	9 ms	3036 KB	Output is correct
5	Correct	12 ms	3676 KB	Output is correct
6	Correct	8 ms	2908 KB	Output is correct
7	Correct	9 ms	3160 KB	Output is correct
8	Correct	15 ms	3776 KB	Output is correct
9	Correct	11 ms	3420 KB	Output is correct
10	Correct	9 ms	2780 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2508 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2392 KB	Output is correct
23	Correct	1 ms	2396 KB	Output is correct
24	Correct	1 ms	2508 KB	Output is correct
25	Correct	1 ms	2392 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2768 KB	Output is correct
2	Correct	18 ms	4188 KB	Output is correct
3	Correct	16 ms	3932 KB	Output is correct
4	Correct	13 ms	2908 KB	Output is correct
5	Correct	23 ms	4804 KB	Output is correct
6	Correct	25 ms	4828 KB	Output is correct
7	Correct	12 ms	3420 KB	Output is correct
8	Correct	14 ms	3648 KB	Output is correct
9	Correct	8 ms	2904 KB	Output is correct
10	Correct	9 ms	2908 KB	Output is correct
11	Correct	10 ms	3012 KB	Output is correct
12	Correct	9 ms	2908 KB	Output is correct
13	Correct	13 ms	3676 KB	Output is correct
14	Correct	10 ms	2916 KB	Output is correct
15	Correct	9 ms	3012 KB	Output is correct
16	Correct	17 ms	3668 KB	Output is correct
17	Correct	11 ms	3420 KB	Output is correct
18	Correct	9 ms	2908 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	1 ms	2524 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	1 ms	2456 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	2396 KB	Output is correct
26	Correct	1 ms	2396 KB	Output is correct
27	Correct	1 ms	2396 KB	Output is correct
28	Correct	1 ms	2512 KB	Output is correct
29	Correct	1 ms	2396 KB	Output is correct
30	Correct	1 ms	2396 KB	Output is correct
31	Correct	1 ms	2396 KB	Output is correct
32	Correct	1 ms	2508 KB	Output is correct
33	Correct	1 ms	2396 KB	Output is correct