DMPG '19 G2 - Test Marks

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 3.5s
Memory limit: 512M

Author:
Problem type

Bob hasn't been doing well in school lately, so his parents have decided to create an incentive to motivate him. Bob will be given some money depending on his results on the next N tests. The tests are ordered and labelled from 1 to N and the j^\text{th} test has already been assigned a value v_j by Bob's parents where v is a non-decreasing sequence. They have promised that for each test j, they will award him with v_j times the number of his marks among the earlier j-1 marks which he exceeded. In other words, if Bob's marks on the N tests are m_1, m_2, \dots, m_N, then Bob will earn

\displaystyle \sum_{\substack{i<j\\ m_i<m_j}} v_j

Bob knows that his mark on a given test is directly proportional to the amount of effort he puts into that test and that this amount of effort is always a non-negative integer. He also knows that he has a limited total amount of effort E. Can you help Bob determine how much money he can make?

Constraints

1 \le v_i \le 1\,000 for all 1 \le i \le N
v_1 \le v_2 \le \dots \le v_N

Subtask 1 [20%]

1 \le N \le 50
0 \le E \le 1\,000

Subtask 2 [30%]

1 \le N \le 200
0 \le E \le 5\,000

Subtask 3 [50%]

1 \le N \le 1\,000
0 \le E \le 20\,000

Input Specification

The first line contains two space-separated integers, N and E.
The next line contains N space-separated integers, v_1, v_2, \dots, v_N.

Output Specification

Output a single integer, the maximum amount of money Bob can earn.

Sample Input 1

3 2
1 2 3

Sample Output 1

6

Explanation for Sample 1

Bob should put 0 effort into the first two tests and 2 effort into the last test. That way, he earns 0\cdot v_1 + 0\cdot v_2 + 2\cdot v_3 = 6.

Sample Input 2

5 0
100 100 100 100 100

Sample Output 2

0

Comments

There are no comments at the moment.