DMOPC '18 Contest 5 P3 - A Familiar Problem

View as PDF

Submit solution

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

Problem type

For her birthday, Mimi received a set of N pencil crayons. Mimi loves her beautiful pencil crayons. In fact, she loves them so much that she assigned each of them individual names, a backstory, and also a cuteness number, C_i.

One day, Mimi lent out her pencil crayons for an art class assignment. When the class ended, her friend returned the pencil crayons in a neat row. Mimi then asked her a curious question:

What is the longest contiguous subsequence where the sum of the cuteness numbers is strictly less than M?

Can you answer her question?


For all subtasks:

1 \leq C_i \leq 10^9

1 \leq M \leq 10^{18}

Subtask 1 [10%]

1 \leq N \leq 100

Subtask 2 [20%]

1 \leq N \leq 2\,000

Subtask 3 [70%]

1 \leq N \leq 200\,000

Input Specification

The first line of input will contain two space-separated integers, N and M.
The second line of input will contain N space-separated integers, C_1, C_2, \dots, C_N.

Output Specification

A single integer, the length of the longest subarray where the sum of the cuteness numbers is strictly less than M.

Sample Input

5 3
1 1 1 2 3

Sample Output



There are no comments at the moment.