JDCC '17 Contest 1 S3 - Great Odds

View as PDF

Submit solution

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

Problem type

While Vlad is giving out unhealthy amounts of candy to trick or treaters, his daughter Vera will be roaming the nearby neighbourhoods to get as much candy as she possibly can.

There are \(N\)​ ​neighbourhoods in Vera’s town, and a trick or treater can expect different amounts of candy from each neighbourhood. Vera will start her evening at the first neighbourhood and trick or treat for \(​T​\) ​minutes. At any minute, she can stay and trick or treat in her current neighbourhood, or move to the next neighbourhood. Vera can end her evening in any neighbourhood (Her dad will pick her up in his spoooky car).

If Vera chooses which neighbourhoods to trick or treat in optimally, how much candy can she expect to get?

Input Specification

The first line of input contains two integers \(N​, T\ (1 \le N, T \le 100\ 000)\), the number of neighbourhoods in Vera’s town and how much time she has to trick or treat.

The next line contains \(N\)​ ​integers in the range \(1 \ldots 100\), with the \(K^{th}\)​ ​integer representing the number of candies per minute that a trick or treater can expect in the \(K​^{th}\) neighbourhood.

For \(50\%\) of cases, \(1 \le N,​ T \le 100\) will hold.

Output

The maximum amount of candy that Vera can expect to get.

Sample​ ​Input​ ​1

3 5
1 5 6

Sample​ ​Output​ ​1

20

Sample​ ​Input​ ​2

4 10
3 4 1 20

Sample​ ​Output​ ​2

140

Comments

There are no comments at the moment.