POTATOPL - Plant the potatoes

no tags 

You have a sack of n potatoes and a strip of land (n + 1) ⋅ k centimeters long.

You want to evenly plant the potatoes on this strip. If we mark the beginning of the strip as centimeter 0, then you want to plant the first potato at centimeter k, plant the second potato at centimeter 2k, ..., plant the n-th potato at centimeter nk (and then the strip of land ends at (n + 1) ⋅ k centimeters).

Each potato has a growth range ri. This means that if you plant the potato at centimeter x, and it has enough space, it will grow you some new tasty potatoes all across [x − ri, x + ri].

However, a potato will never grow over another potato's growth territory, or beyond your strip of land - in other words, if the potato comes across the edge of the plot or bumps into a different potato plant, it stops growing in that direction.

Given n, k and ri of your n potatoes, how many potatoes can you grow if you plant them optimally?


The first line contains an integer 1 ≤ T ≤ 20 - the number of test cases. T test cases follow.

For each test case:

The first line contains the integers 1 ≤ n ≤ 106 and 1 ≤ k ≤ 109. The second line contains n integers 1 ≤ ri ≤ k - the growth radii of the potatoes.

The sum of n within an input file will never exceed 2 ⋅ 106.


For each test case, output a single integer: the maximum length of strip you can cover in grown potatoes.



3 20
6 12 4
3 20
12 12 12
3 5
1 1 5



In the first case, if we plant the potatoes in the same order as in the input, that is 6->20cm, 12->40cm, 4->60cm, they will grow on [14,26], [28,52], [56,64] for a total of 12+24+8 = 44 cm of potatoes. Any other order works just as well, though.

In the second case we don't really have much to choose from.. The potatoes would want to grow out to [8,32], [28,52], [48,72], but they get in each other's way. So they will end up growing on [8,30], [30,50], [50,72] for a total of 64cm.

In the last case the best order to plant the potatoes is, for example, 5 1 1.

hide comments
Vipul Srivastava: 2019-05-22 22:37:33

Loved this problem +5

Added by:Hodobox
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem