Mock CCO '18 Contest 2 Problem 1 - Victor Runs

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.18s
Memory limit: 16M

Problem type

Victor, as a mathematician, reasons best in K dimensions. What happens if he is made to reason in one dimension?

Victor's gym teacher, Roger, has set up an obstacle course of sorts for Victor. The obstacle course is modeled after the number line, with checkpoints at one of N locations. Victor has T seconds to get to as many checkpoints as possible. Victor can run at the speed of one unit per second. If Victor first reaches a checkpoint t seconds into the obstacle course, Victor earns \max(0, T-t) points. Victor starts at the origin and can end at any location.

Compute the maximum number of points Victor can earn, given the configuration Roger has set up for him.


N \le 300

T \le 10^6

\left|x_i\right| \le 10^4

All x_i are distinct.

Input Specification

The first line will contain two space-separated integers, N and T.

Each of the next N lines will contain a single integer, x_i, representing one of the locations where a checkpoint is located at.

Output Specification

Print, on a single line, the maximum score Victor can obtain if he runs optimally.

Sample Input

3 15

Sample Output



There are no comments at the moment.