BSSPC '22 P4 - Exec Pieing

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

After losing the execs vs. members jeopardy, the execs have lined up to be pied in the face by Derrick (totally consensually of course, why else would they be lined up?)

There are only T minutes of the kickoff left for Derrick to pie all the execs. Of the N execs in line, when it comes to their turn, the i^\text{th} exec in line will run/hide/stall for t_i minutes before accepting their fate and getting pied.

Derrick must pie the execs in the order they are lined up. However, before this, he must choose exactly one exec to remove from the line, to help him with the whipped cream. What is the maximum number of execs Derrick can pie in the time allotted?


2 \le N \le 2 \times 10^5

1 \le T \le 2 \times 10^9

1 \le t_i \le 10^4

Subtask 1 [50%]

2 \le N \le 10^3

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains two integers, N and T.

The next line contains N space-separated integers, the i^{th} being t_i.

Output Specification

Output a single integer, the maximum number of execs Derrick can pie.

Sample Input

4 5
2 7 3 1

Sample Output



Derrick can choose to remove the second exec from the line.

This allows him to spend 2+3 = 5 minutes pieing the first and third execs, after which he runs out of time.


There are no comments at the moment.