CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Skyline
Sender:aalto2024i_006
Submission time:2024-10-30 16:27:18 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.01 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.01 sdetails
#31ACCEPTED0.01 sdetails
#32ACCEPTED0.01 sdetails
#33ACCEPTED0.01 sdetails
#34ACCEPTED0.01 sdetails
#35ACCEPTED0.01 sdetails
#36ACCEPTED0.01 sdetails
#37ACCEPTED0.01 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.01 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.01 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.01 sdetails
#49ACCEPTED0.01 sdetails
#50ACCEPTED0.01 sdetails
#51ACCEPTED0.07 sdetails
#52ACCEPTED0.07 sdetails
#53ACCEPTED0.07 sdetails
#54ACCEPTED0.07 sdetails

Code

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

string to_string(string s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void debug_out() {
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit); // RTE if input wrong datatype

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    const int M = 1e6 + 5;
    bitset<M> can;
    can[0] = 1;
    for (int i = 0; i < n; i++) {
        can |= can << a[i];
    }

    while (q--) {
        int b;
        cin >> b;

        cout << (can[b] ? "Yes " : "No "); 
    }
}

Test details

Test 1

Verdict: ACCEPTED

input
1 20

29 43 23 70 56 72 72 50 43 79 ...

correct output
No No No No No No No No No No ...

user output
No No No No No No No No No No ...

Test 2

Verdict: ACCEPTED

input
2 20
8 8 
6 38 42 31 55 41 90 8 74 92 72...

correct output
No No No No No No No Yes No No...

user output
No No No No No No No Yes No No...

Test 3

Verdict: ACCEPTED

input
2 20
8 10 
67 92 41 94 85 41 87 67 71 1 2...

correct output
No No No No No No No No No No ...

user output
No No No No No No No No No No ...

Test 4

Verdict: ACCEPTED

input
3 20
8 8 10 
58 60 46 57 39 26 28 19 67 99 ...

correct output
No No No No No Yes No No No No...

user output
No No No No No Yes No No No No...

Test 5

Verdict: ACCEPTED

input
3 20
1 7 8 
30 69 38 80 10 38 83 43 83 65 ...

correct output
No No No No No No No No No No ...

user output
No No No No No No No No No No ...

Test 6

Verdict: ACCEPTED

input
3 20
10 4 3 
83 7 5 38 11 99 60 10 53 61 42...

correct output
No Yes No No No No No Yes No N...

user output
No Yes No No No No No Yes No N...

Test 7

Verdict: ACCEPTED

input
4 20
1 9 5 2 
18 36 87 78 99 50 94 76 29 43 ...

correct output
No No No No No No No No No No ...

user output
No No No No No No No No No No ...

Test 8

Verdict: ACCEPTED

input
4 20
1 7 4 7 
79 78 78 48 66 96 96 100 6 84 ...

correct output
No No No No No No No No No No ...

user output
No No No No No No No No No No ...

Test 9

Verdict: ACCEPTED

input
4 20
8 10 8 2 
22 50 48 68 61 28 20 26 95 53 ...

correct output
No No No No No Yes Yes Yes No ...

user output
No No No No No Yes Yes Yes No ...

Test 10

Verdict: ACCEPTED

input
4 20
6 1 9 10 
16 91 9 41 27 20 58 31 19 20 9...

correct output
Yes No Yes No No Yes No No Yes...

user output
Yes No Yes No No Yes No No Yes...

Test 11

Verdict: ACCEPTED

input
5 20
6 8 9 7 9 
55 85 43 63 65 39 44 30 90 6 9...

correct output
No No No No No Yes No Yes No Y...

user output
No No No No No Yes No Yes No Y...

Test 12

Verdict: ACCEPTED

input
5 20
10 8 10 1 2 
31 100 15 24 10 40 19 39 35 67...

correct output
Yes No No No Yes No Yes No No ...

user output
Yes No No No Yes No Yes No No ...

Test 13

Verdict: ACCEPTED

input
5 20
2 1 10 6 10 
44 49 43 33 34 16 21 70 62 12 ...

correct output
No No No No No Yes Yes No No Y...

user output
No No No No No Yes Yes No No Y...

Test 14

Verdict: ACCEPTED

input
5 20
1 8 9 3 2 
52 57 90 44 90 2 13 5 21 25 6 ...

correct output
No No No No No Yes Yes Yes Yes...

user output
No No No No No Yes Yes Yes Yes...

Test 15

Verdict: ACCEPTED

input
5 20
10 6 2 10 9 
72 61 70 60 22 15 98 23 1 70 2...

correct output
No No No No Yes Yes No No No N...

user output
No No No No Yes Yes No No No N...

Test 16

Verdict: ACCEPTED

input
5 20
2 10 10 4 4 
92 98 49 9 62 40 77 36 52 49 3...

correct output
No No No No No No No No No No ...

user output
No No No No No No No No No No ...

Test 17

Verdict: ACCEPTED

input
5 20
10 4 3 9 1 
5 38 11 99 60 10 53 61 42 54 3...

correct output
Yes No Yes No No Yes No No No ...

user output
Yes No Yes No No Yes No No No ...

Test 18

Verdict: ACCEPTED

input
5 20
4 8 4 6 10 
73 46 98 31 54 27 51 9 8 42 27...

correct output
No No No No No No No No Yes No...

user output
No No No No No No No No Yes No...

Test 19

Verdict: ACCEPTED

input
5 20
1 10 3 9 4 
54 82 24 43 2 62 44 77 41 41 5...

correct output
No No Yes No No No No No No No...

user output
No No Yes No No No No No No No...

Test 20

Verdict: ACCEPTED

input
5 20
4 6 6 6 2 
14 32 15 2 22 88 42 14 25 14 9...

correct output
Yes No No Yes Yes No No Yes No...

user output
Yes No No Yes Yes No No Yes No...

Test 21

Verdict: ACCEPTED

input
10 20
6 8 9 7 9 6 9 5 7 7 
39 44 30 90 6 97 28 39 48 80 8...

correct output
Yes Yes Yes No Yes No Yes Yes ...

user output
Yes Yes Yes No Yes No Yes Yes ...

Test 22

Verdict: ACCEPTED

input
10 20
10 8 10 1 2 4 10 2 3 1 
40 19 39 35 67 40 94 54 85 42 ...

correct output
Yes Yes Yes Yes No Yes No No N...

user output
Yes Yes Yes Yes No Yes No No N...

Test 23

Verdict: ACCEPTED

input
10 20
2 1 10 6 10 5 5 5 4 4 
16 21 70 62 12 30 49 27 64 63 ...

correct output
Yes Yes No No Yes Yes Yes Yes ...

user output
Yes Yes No No Yes Yes Yes Yes ...

Test 24

Verdict: ACCEPTED

input
10 20
1 8 9 3 2 6 6 9 5 9 
2 13 5 21 25 6 10 45 70 3 15 4...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 25

Verdict: ACCEPTED

input
10 20
10 6 2 10 9 8 7 7 6 3 
15 98 23 1 70 26 91 44 64 78 1...

correct output
Yes No Yes No No Yes No Yes No...

user output
Yes No Yes No No Yes No Yes No...

Test 26

Verdict: ACCEPTED

input
10 20
2 10 10 4 4 10 10 6 2 8 
40 77 36 52 49 30 100 19 81 9 ...

correct output
Yes No Yes Yes No Yes No No No...

user output
Yes No Yes Yes No Yes No No No...

Test 27

Verdict: ACCEPTED

input
10 20
10 4 3 9 1 1 4 2 10 6 
10 53 61 42 54 34 49 63 83 44 ...

correct output
Yes No No Yes No Yes Yes No No...

user output
Yes No No Yes No Yes Yes No No...

Test 28

Verdict: ACCEPTED

input
10 20
4 8 4 6 10 8 6 10 4 6 
27 51 9 8 42 27 2 50 53 68 87 ...

correct output
No No No Yes Yes No No Yes No ...

user output
No No No Yes Yes No No Yes No ...

Test 29

Verdict: ACCEPTED

input
10 20
1 10 3 9 4 6 9 3 5 1 
62 44 77 41 41 53 88 48 93 56 ...

correct output
No Yes No Yes Yes No No Yes No...

user output
No Yes No Yes Yes No No Yes No...

Test 30

Verdict: ACCEPTED

input
10 20
4 6 6 6 2 2 4 2 2 4 
88 42 14 25 14 9 40 35 50 17 3...

correct output
No No Yes No Yes No No No No N...

user output
No No Yes No Yes No No No No N...

Test 31

Verdict: ACCEPTED

input
100 1000
59286 71521 84428 60278 85796 ...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 32

Verdict: ACCEPTED

input
100 1000
99721 72034 93258 12 12813 302...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 33

Verdict: ACCEPTED

input
100 1000
18509 2593 93156 54968 94775 4...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 34

Verdict: ACCEPTED

input
100 1000
7073 70816 83997 29091 12134 5...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 35

Verdict: ACCEPTED

input
100 1000
90064 54725 17270 97270 85564 ...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 36

Verdict: ACCEPTED

input
100 1000
5520 87074 83134 20672 36374 9...

correct output
No No Yes No No Yes Yes No Yes...

user output
No No Yes No No Yes Yes No Yes...

Test 37

Verdict: ACCEPTED

input
100 1000
94750 33199 20941 82125 6426 4...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 38

Verdict: ACCEPTED

input
100 1000
22734 77994 31898 43842 97824 ...

correct output
No Yes No No No Yes No Yes No ...

user output
No Yes No No No Yes No Yes No ...

Test 39

Verdict: ACCEPTED

input
100 1000
1112 96856 23945 86921 37753 5...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 40

Verdict: ACCEPTED

input
100 1000
36448 50188 49914 49578 756 13...

correct output
Yes Yes No Yes No Yes Yes Yes ...

user output
Yes Yes No Yes No Yes Yes Yes ...

Test 41

Verdict: ACCEPTED

input
200 1000
59286 71521 84428 60278 85796 ...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 42

Verdict: ACCEPTED

input
200 1000
99721 72034 93258 12 12813 302...

correct output
Yes Yes No Yes Yes Yes Yes Yes...

user output
Yes Yes No Yes Yes Yes Yes Yes...

Test 43

Verdict: ACCEPTED

input
200 1000
18509 2593 93156 54968 94775 4...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 44

Verdict: ACCEPTED

input
200 1000
7073 70816 83997 29091 12134 5...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 45

Verdict: ACCEPTED

input
200 1000
90064 54725 17270 97270 85564 ...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 46

Verdict: ACCEPTED

input
200 1000
5520 87074 83134 20672 36374 9...

correct output
No No No No No No No No Yes No...

user output
No No No No No No No No Yes No...

Test 47

Verdict: ACCEPTED

input
200 1000
94750 33199 20941 82125 6426 4...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 48

Verdict: ACCEPTED

input
200 1000
22734 77994 31898 43842 97824 ...

correct output
No Yes No No Yes Yes Yes Yes Y...

user output
No Yes No No Yes Yes Yes Yes Y...

Test 49

Verdict: ACCEPTED

input
200 1000
1112 96856 23945 86921 37753 5...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 50

Verdict: ACCEPTED

input
200 1000
36448 50188 49914 49578 756 13...

correct output
Yes Yes No Yes No No No Yes No...

user output
Yes Yes No Yes No No No Yes No...

Test 51

Verdict: ACCEPTED

input
2000 100000
59286 71521 84428 60278 85796 ...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 52

Verdict: ACCEPTED

input
2000 100000
99721 72034 93258 12 12813 302...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 53

Verdict: ACCEPTED

input
2000 100000
18509 2593 93156 54968 94775 4...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...

Test 54

Verdict: ACCEPTED

input
2000 100000
7073 70816 83997 29091 12134 5...

correct output
Yes Yes Yes Yes Yes Yes Yes Ye...

user output
Yes Yes Yes Yes Yes Yes Yes Ye...