CF1862E.Kolya and Movie Theatre
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Recently, Kolya found out that a new movie theatre is going to be opened in his city soon, which will show a new movie every day for n days. So, on the day with the number 1≤i≤n , the movie theatre will show the premiere of the i -th movie. Also, Kolya found out the schedule of the movies and assigned the entertainment value to each movie, denoted by ai .
However, the longer Kolya stays without visiting a movie theatre, the larger the decrease in entertainment value of the next movie. That decrease is equivalent to d⋅cnt , where d is a predetermined value and cnt is the number of days since the last visit to the movie theatre. It is also known that Kolya managed to visit another movie theatre a day before the new one opened — the day with the number 0 . So if we visit the movie theatre the first time on the day with the number i , then cnt — the number of days since the last visit to the movie theatre will be equal to i .
For example, if d=2 and a=[3,2,5,4,6] , then by visiting movies with indices 1 and 3 , cnt value for the day 1 will be equal to 1−0=1 and cnt value for the day 3 will be 3−1=2 , so the total entertainment value of the movies will be a1−d⋅1+a3−d⋅2=3−2⋅1+5−2⋅2=2 .
Unfortunately, Kolya only has time to visit at most m movies. Help him create a plan to visit the cinema in such a way that the total entertainment value of all the movies he visits is maximized.
输入格式
Each test consists of multiple test cases. The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains three integers n , m , and d ( 1≤n≤2⋅105 , 1≤m≤n , 1≤d≤109 ).
The second line of each set of input data contains n integers a1,a2,…,an ( −109≤ai≤109 ) — the entertainment values of the movies.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, output a single integer — the maximum total entertainment value that Kolya can get.
输入输出样例
输入#1
6 5 2 2 3 2 5 4 6 4 3 2 1 1 1 1 6 6 6 -82 45 1 -77 39 11 5 2 2 3 2 5 4 8 2 1 1 -1 2 6 3 2 -8 8 -2 -1 9 0
输出#1
2 0 60 3 0 7
说明/提示
The first test case is explained in the problem statement.
In the second test case, it is optimal not to visit any movies.
In the third test case, it is optimal to visit movies with numbers 2 , 3 , 5 , 6 , so the total entertainment value of the visited movies will be 45−6⋅2+1−6⋅1+39−6⋅2+11−6⋅1=60 .