CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Roller coaster
Sender:aalto2024i_004
Submission time:2024-10-30 17:43:49 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.04 sdetails
#30.04 sdetails
#40.03 sdetails
#50.01 sdetails
#60.03 sdetails
#70.01 sdetails
#80.02 sdetails
#90.03 sdetails
#100.04 sdetails
#110.02 sdetails
#120.03 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:

input
3
1000 5 5 0
20 20 20 50
50 50 0 99

correct output
145

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

Test 2

Verdict:

input
10
1000000 1000000 1000000 99
1000000 1000000 1000000 99
1000000 1000000 1000000 99
1000000 1000000 1000000 99
...

correct output
2010101010101010100000000

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

Test 3

Verdict:

input
7
794772 933488 441001 5
271493 536110 509532 51
962838 821872 870163 38
499748 375441 611720 27
...

correct output
19316405

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

Test 4

Verdict:

input
3
596853 888598 841235 97
66172 267459 123646 63
797926 471325 495185 83

correct output
81642158

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

Test 5

Verdict:

input
1
96033 88994 378596 21

correct output
96033

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

Test 6

Verdict:

input
4
621429 570665 136758 47
960437 633256 497081 80
609067 68711 635017 1
952965 878149 492025 33

correct output
19366822

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

Test 7

Verdict:

input
4
318031 108177 756250 50
502140 162500 94476 8
20779 421098 576089 37
839335 802331 61705 28

correct output
6474336

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

Test 8

Verdict:

input
10
267853 777820 375951 88
988230 882388 775839 83
967127 555787 30414 59
813651 989181 261150 83
...

correct output
114240784216

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

Test 9

Verdict:

input
10
861881 84483 508595 97
274330 38611 473 18
695015 614973 493097 97
770531 391287 334900 98
...

correct output
26667465547194

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

Test 10

Verdict:

input
6
993908 158176 414002 83
50631 75954 861168 68
98702 383452 611097 7
953893 532084 225127 4
...

correct output
46921821

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

Test 11

Verdict:

input
4
388404 393603 132467 24
739054 45905 89323 17
259460 850672 530957 26
420175 673047 31765 58

correct output
2895218

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

Test 12

Verdict:

input
8
643002 391445 280110 17
195187 908655 709512 0
354760 527205 486247 77
84740 350249 581194 78
...

correct output
250399569

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