CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Skyline
Sender:aalto2024i_004
Submission time:2024-10-30 17:33:32 +0200
Language:C++ (C++17)
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.01 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.01 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.01 sdetails
#26ACCEPTED0.01 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.01 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.10 sdetails
#52ACCEPTED0.10 sdetails
#53ACCEPTED0.10 sdetails
#54ACCEPTED0.10 sdetails

Code

// ~/.vim/cpp_template.cpp
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>

#define REP(i,a,b) for (int i = a; i < b; i++)

// Type Aliases for 1D and 2D vectors with initialization
#define vi(n, val) vector<int>(n, val) // 1D vector of ints with size n, initialized to val
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

#define LL_INF std::numeric_limits<long long int>::max()
#define INF std::numeric_limits<int>::max()


using namespace std;


template <typename T>
void pV(const std::vector<T>& vec, const std::string& label = "Vector") {
    std::cout << label << ": [ ";
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << "]" << std::endl;
}


void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {
    if ((*visited)[s]) return;
    (*visited)[s] = true;
    // process node s


    for (auto u: (*adj)[s]) {
        dfs(u, visited, adj);
    }
}
/*
// DEPTH-FRIRST-SEARCH
vector<int> adj[N];                                                          
vector<bool> visited(N, false);
int u, v;
for(int i = 0; i < M;i++){
    cin >> u >> v;
    u--;
    v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
}
*/

vector<long long> dijkstra(int N, int x, vector<vector<pair<int,int>>> *adj){
    vector<bool> processed(N, false);
    vector<long long> distance(N, LL_INF);
    priority_queue<pair<long long,int>> q;
    //for (int i = 1; i <= n; i++) distance[i] = INF;
    distance[x] = 0;
    q.push({0,x});
    while (!q.empty()) {
        int a = q.top().second; q.pop();
        if (processed[a]) continue;
        processed[a] = true;
        for (auto u : (*adj)[a]) {
            int b = u.first, w = u.second;
            if (distance[a]+w < distance[b]) {
                distance[b] = distance[a]+w;
                q.push({-distance[b],b});
            }
        }
    }
    return distance;


}


/*
DIJKSTRA
//vector<vector<pair<int,int>>> adj(N, vector<pair<int, int>>(N));
*/

int MAX = 1e6+1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // Your code starts here
    int n, q;
    cin >> n >> q;
    vector<int> as(n, 0);
    REP(i, 0, n){
        cin >> as[i];
    }

    vector<bool> prev(MAX, false), curr(MAX, false);

    bitset<1000005> dp;
    dp[0] = 1;

    for(int h: as) {
        dp |= dp << h;
    }
    REP(i, 0, q){
        int temp;
        cin >> temp;
        if(dp[temp]){
            cout << "Yes ";
        }else{
            cout << "No ";
        }
    }
    cout << endl;


    


    return 0;
}


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