DMOPC '18 Contest 2 P4 - Damage Output

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Mimi is playing more Enur Yrotcaf 4, when she realizes that her damage output is...subpar.

Being a meticulous player, she has tracked her damage output over the last N seconds, and decides to take a contiguous subsection where her damage output is at least M.

Wanting to show off to her friends, she wants this interval to be as short as possible. Can you help her find the length of the smallest interval where she deals at least M damage?


For all subtasks, 1 \leq M \leq 10^{18}.
Additionally, Mimi will deal at least 0 damage, and at most 10^9 units of damage per second.

Subtask 1 [10%]

1 \leq N \leq 800

Subtask 2 [30%]

1 \leq N \leq 5\,000

Subtask 3 [60%]

1 \leq N \leq 500\,000

Input Specification

The first line of input will contain two space-separated integers, N and M.
The next line of input will contain N space-separated integers, d_1, d_2, \ldots, d_N, where d_i is how much damage Mimi deals at time i.

Output Specification

The smallest integer L such that there is a contiguous subarray of length L where Mimi deals at least M total damage, or -1 if no such subarray exists.

Sample Input 1

5 6
1 3 2 5 0

Sample Output 1


Sample Input 2

5 30
1 2 3 4 5

Sample Output 2