Amplitude Hackathon '23 Practice Problem 3 - Demo Day Demos - Olympiads Online Judge

Amplitude Hackathon '23 Practice Problem 3 - Demo Day Demos

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 1G

Problem type

It's Demo Day! There are $N$ ~N~ demos but unfortunately there are only $K$ ~K~ picoseconds allocated, so it might not be possible for every demo to be shown. Assuming that one demo can start precisely when another demo ends, what is the maximum number of demos that can be shown?

Constraints

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

$1 \le a_i, K \le 10^{18}$ ~1 \le a_i, K \le 10^{18}~

Subtask 1 [1 point]

$N \le 10^3$ ~N \le 10^3~

$a_i, K \le 10^6$ ~a_i, K \le 10^6~

Subtask 2 [1 point]

No additional constraints.

Input Specification

The first line of input contains two integers $N$ ~N~ and $K$ ~K~.

The second line contains $N$ ~N~ integers, where $a_i$ ~a_i~ represents the number of picoseconds needed for demo $i$ ~i~.

Output Specification

Output the maximum number of demos that can be shown.

Sample Input

3 5
3 2 1

Sample Output

Sample Explanation

We can show the first two demos. It is impossible to show all three demos, as that would take 6 picoseconds.

Comments

0

sre0x2a commented on March 24, 2026, 7:52 p.m.

Does the input data set contain extra whitespace between the numbers?

0
do_ur_homwork commented on March 24, 2026, 8:42 p.m.
theres only one i think...

3 5 3 2 1

is an example of how the data looks like. If its not make a ticket or smth