CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Skyline
Sender:aalto2024i_007
Submission time:2024-10-30 17:44:46 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#70.00 sdetails
#8ACCEPTED0.00 sdetails
#90.00 sdetails
#100.00 sdetails
#11ACCEPTED0.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#16ACCEPTED0.00 sdetails
#170.00 sdetails
#18ACCEPTED0.00 sdetails
#190.00 sdetails
#200.01 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#26ACCEPTED0.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#30ACCEPTED0.00 sdetails
#310.01 sdetails
#320.01 sdetails
#330.01 sdetails
#340.01 sdetails
#350.01 sdetails
#360.01 sdetails
#370.01 sdetails
#380.01 sdetails
#390.01 sdetails
#400.01 sdetails
#410.01 sdetails
#420.01 sdetails
#430.01 sdetails
#440.01 sdetails
#450.01 sdetails
#460.01 sdetails
#470.01 sdetails
#480.01 sdetails
#490.01 sdetails
#500.01 sdetails
#51--details
#52--details
#53--details
#54--details

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

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

    // Sort the rocks to utilize in binary search/prefix sums
    sort(rocks.begin(), rocks.end());
    vector<long long> prefixSums(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        prefixSums[i] = prefixSums[i - 1] + rocks[i - 1];
    }

    for (int height : tower_heights) {
        if (height > prefixSums[n]) {
            cout << "No ";
            continue;
        }

        // Binary search in prefix sums to find any close or exact match
        bool canBuild = false;
        for (int i = 0; i < n && !canBuild; i++) {
            int lo = i + 1, hi = n;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                long long sum = prefixSums[mid] - prefixSums[i];
                if (sum == height) {
                    canBuild = true;
                    break;
                } else if (sum < height) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }

        if (canBuild) {
            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:

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:

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 No Yes No N...

Test 10

Verdict:

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 No 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:

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

Test 13

Verdict:

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

Test 14

Verdict:

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

Test 15

Verdict:

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

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:

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
No No No No No Yes No 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:

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

Test 20

Verdict:

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
No No No Yes Yes No No No No N...

Test 21

Verdict:

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
No Yes No No Yes No No No No N...

Test 22

Verdict:

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:

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

Test 24

Verdict:

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 No Yes No Yes Yes Yes No N...

Test 25

Verdict:

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 No 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:

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 No No No Yes No No N...

Test 28

Verdict:

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

Test 29

Verdict:

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 No No Yes Yes No No No No N...

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:

input
100 1000
59286 71521 84428 60278 85796 ...

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

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

Test 32

Verdict:

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

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

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

Test 33

Verdict:

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

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

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

Test 34

Verdict:

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

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

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

Test 35

Verdict:

input
100 1000
90064 54725 17270 97270 85564 ...

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

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

Test 36

Verdict:

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

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

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

Test 37

Verdict:

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

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

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

Test 38

Verdict:

input
100 1000
22734 77994 31898 43842 97824 ...

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

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

Test 39

Verdict:

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

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

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

Test 40

Verdict:

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

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

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

Test 41

Verdict:

input
200 1000
59286 71521 84428 60278 85796 ...

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

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

Test 42

Verdict:

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

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

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

Test 43

Verdict:

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

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

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

Test 44

Verdict:

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

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

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

Test 45

Verdict:

input
200 1000
90064 54725 17270 97270 85564 ...

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

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

Test 46

Verdict:

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

Test 47

Verdict:

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

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

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

Test 48

Verdict:

input
200 1000
22734 77994 31898 43842 97824 ...

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

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

Test 49

Verdict:

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

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

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

Test 50

Verdict:

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

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

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

Test 51

Verdict:

input
2000 100000
59286 71521 84428 60278 85796 ...

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

user output
(empty)

Test 52

Verdict:

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

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

user output
(empty)

Test 53

Verdict:

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

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

user output
(empty)

Test 54

Verdict:

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

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

user output
(empty)