DMOPC '18 Contest 2 P4 - Damage Output - Olympiads Online Judge

DMOPC '18 Contest 2 P4 - Damage Output

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

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$ $N$ seconds, and decides to take a contiguous subsection where her damage output is at least $M$ $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$ $M$ damage?

Constraints

For all subtasks:

$1 \le M \le 10^{18}$ $1 \leq M \leq 10^{18}$

Mimi will deal at least $0$ $0$ damage, and at most $10^9$ $10^{9}$ units of damage per second.

Subtask 1 [10%]

$1 \le N \le 800$ $1 \leq N \leq 800$

Subtask 2 [30%]

$1 \le N \le 5\,000$ $1 \leq N \leq 5 000$

Subtask 3 [60%]

$1 \le N \le 500\,000$ $1 \leq N \leq 500 000$

Input Specification

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

Output Specification

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

Sample Input 1

Copy

5 6
1 3 2 5 0

Sample Output 1

Copy

Sample Input 2

Copy

5 30
1 2 3 4 5

Sample Output 2

Copy

-1

Comments

-4

maxcruickshanks commented on Oct. 21, 2022, 9:44 p.m.

Since the original data were weak, two test cases were added, and all non-contest submissions were rejudged.