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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, C_3, \ldots, 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.