답안 #932928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932928	2024-02-24T14:43:41 Z	asdasdqwer	Martian DNA (BOI18_dna)	C++14	100 / 100	89 ms	4924 KB

dna

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

signed main() {
    int n,k,r;cin>>n>>k>>r;
    vector<int> a(n);
    for (auto &x:a)cin>>x;
    vector<int> req(n, 0);
    for (int i=0;i<r;i++) {
        int c1,c2;cin>>c1>>c2;
        req[c1] += c2;
    }

    vector<int> cnt(n, 0);
    for (auto &x:a)cnt[x]++;
    for (int i=0;i<n;i++) {
        if (req[i] > cnt[i]) {
            cout<<"impossible\n";
            return 0;
        }
    }

    int p1 = 0, p2 = -1;

    int sat = 0;
    cnt.assign(n,0);

    for (; p1 < n; p1++) {
        cnt[a[p1]]++;
        if (cnt[a[p1]] == req[a[p1]]) {
            sat++;
        }

        if (sat == r) {
            break;
        }
    }

    int minLen = p1 - p2;

    for (; p1<n;) {
        while (p2+1 < n && cnt[a[p2+1]]-1 >= req[a[p2+1]]) {
            p2++;
            cnt[a[p2]]--;
        }

        minLen = min(minLen, p1-p2);
        p1++;
        if (p1 != n) {
            cnt[a[p1]]++;
        }
    }

    cout<<minLen<<"\n";
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	440 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	440 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	436 KB	Output is correct
9	Correct	0 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	3004 KB	Output is correct
2	Correct	24 ms	3156 KB	Output is correct
3	Correct	31 ms	2996 KB	Output is correct
4	Correct	23 ms	3160 KB	Output is correct
5	Correct	40 ms	3672 KB	Output is correct
6	Correct	22 ms	3144 KB	Output is correct
7	Correct	25 ms	3256 KB	Output is correct
8	Correct	42 ms	3904 KB	Output is correct
9	Correct	36 ms	3512 KB	Output is correct
10	Correct	23 ms	3396 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	352 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	1 ms	448 KB	Output is correct
16	Correct	1 ms	344 KB	Output is correct
17	Correct	0 ms	356 KB	Output is correct
18	Correct	0 ms	356 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	0 ms	344 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	4520 KB	Output is correct
2	Correct	57 ms	4280 KB	Output is correct
3	Correct	72 ms	4020 KB	Output is correct
4	Correct	25 ms	3152 KB	Output is correct
5	Correct	71 ms	4924 KB	Output is correct
6	Correct	89 ms	4792 KB	Output is correct
7	Correct	38 ms	3784 KB	Output is correct
8	Correct	44 ms	3924 KB	Output is correct
9	Correct	22 ms	3164 KB	Output is correct
10	Correct	23 ms	3140 KB	Output is correct
11	Correct	25 ms	3164 KB	Output is correct
12	Correct	24 ms	3180 KB	Output is correct
13	Correct	52 ms	3904 KB	Output is correct
14	Correct	23 ms	3152 KB	Output is correct
15	Correct	41 ms	3156 KB	Output is correct
16	Correct	46 ms	4020 KB	Output is correct
17	Correct	49 ms	3664 KB	Output is correct
18	Correct	25 ms	3164 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	2 ms	600 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	2 ms	344 KB	Output is correct
24	Correct	1 ms	456 KB	Output is correct
25	Correct	1 ms	432 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	428 KB	Output is correct
29	Correct	1 ms	428 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	344 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct