답안 #731660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731660	2023-04-27T18:10:17 Z	NintsiChkhaidze	Martian DNA (BOI18_dna)	C++17	0 / 100	32 ms	4468 KB

dna

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5,inf=1e9;
int a[N],mn[N],cnt[N];

signed main (){
	
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,k,R;
	cin>>n>>k>>R;
	
	for (int i = 1; i <= n; i++){
		cin>>a[i];
	}
	
	for (int i = 1; i <= k; i++) mn[i] = inf;
	for (int i = 1; i <= R; i++){
		int x,y;
		cin>>x>>y;
		mn[x] = y;
	}
	
	int C = R,r = 1,ans=inf;
	cnt[a[1]]++;
	if (cnt[a[1]] >= mn[a[1]]) --C;
	
	for (int i = 1; i <= n; i++){
		while (C > 0 && r + 1 <= n){
			++r;
			cnt[a[r]]++;
			if (cnt[a[r]] - 1 < mn[a[r]] && cnt[a[r]] >= mn[a[r]]) 
				C--;
		}
		if (C == 0) ans=min(ans,r - i + 1);
		
		int dl = 0;
		if (cnt[a[i]] >= mn[a[i]]) ++dl;
		cnt[a[i]]--;
		if (cnt[a[i]] >= mn[a[i]]) --dl;
		C += dl;
	}
	if(ans==inf) cout<<"impossible";
	else cout<<ans;
}

Subtask #1

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Incorrect	1 ms	340 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	360 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	324 KB	Output is correct
15	Incorrect	1 ms	340 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	1108 KB	Output is correct
2	Correct	14 ms	1484 KB	Output is correct
3	Correct	14 ms	1444 KB	Output is correct
4	Correct	12 ms	1476 KB	Output is correct
5	Correct	17 ms	2800 KB	Output is correct
6	Correct	12 ms	1512 KB	Output is correct
7	Correct	13 ms	1636 KB	Output is correct
8	Correct	21 ms	3828 KB	Output is correct
9	Correct	17 ms	2120 KB	Output is correct
10	Correct	13 ms	1492 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	360 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	328 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	324 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Incorrect	1 ms	340 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	1620 KB	Output is correct
2	Correct	28 ms	3080 KB	Output is correct
3	Correct	21 ms	2852 KB	Output is correct
4	Correct	13 ms	1492 KB	Output is correct
5	Correct	32 ms	3980 KB	Output is correct
6	Correct	32 ms	4468 KB	Output is correct
7	Correct	17 ms	2156 KB	Output is correct
8	Correct	20 ms	2384 KB	Output is correct
9	Correct	12 ms	1488 KB	Output is correct
10	Correct	14 ms	1492 KB	Output is correct
11	Correct	15 ms	1432 KB	Output is correct
12	Correct	15 ms	1492 KB	Output is correct
13	Correct	18 ms	2776 KB	Output is correct
14	Correct	13 ms	1472 KB	Output is correct
15	Correct	13 ms	1612 KB	Output is correct
16	Correct	20 ms	3888 KB	Output is correct
17	Correct	16 ms	2004 KB	Output is correct
18	Correct	13 ms	1508 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 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	340 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	1 ms	324 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Incorrect	1 ms	340 KB	Output isn't correct
34	Halted	0 ms	0 KB	-