CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Skyline
Sender:AleksandrPolitov
Submission time:2024-10-30 16:36:36 +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.00 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.00 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.11 sdetails
#52ACCEPTED0.11 sdetails
#53ACCEPTED0.11 sdetails
#54ACCEPTED0.11 sdetails

Code

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define char unsigned char
#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()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back

#define LSOne(S) ((S) & -(S))

using namespace std;
// mt19937 rnd(239);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); }
typedef long double T;
typedef complex<T> pt;
#define X real()
#define Y imag()

template<class T>
istream& operator>> (istream& is, complex<T>& p) {
    T value;
    is >> value;
    p.real(value);
    is >> value;
    p.imag(value);
    return is;
}

typedef long long ll;
typedef long double ld;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}

const int INF = 1e9; // 10^9 = 1B is < 2^31-1
const ll LLINF = 4e18; // 4*10^18 is < 2^63-1
const double EPS = 1e-9;
const ll MOD = 1e9+7;

const int N=1e6+10;

int solve() {
    bitset<N> dp;
    dp[0]=true;

    int n, q; std::cin >> n >> q;
    for (int i = 0; i < n; i++) {
        ll w; std::cin >> w;
        dp|=dp<<w;
    }

    for (int i = 0; i < q; i++) {
        ll w; std::cin >> w;
        std::cout << (dp[w] ? "Yes" : "No") << " ";
    }

    return 0;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    //cin >> TET;
    for (int i = 1; i <= TET; i++) {
        #ifdef ONPC
            cout << "TEST CASE#" << i << endl;
        #endif
        
        if (solve()) {
            break;
        }

        #ifdef ONPC
            cout << "__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
}

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...