Problem 1305
Maximum income
Time Limit: 1000ms
Memory Limit: 65536kb
One person prefers investing in stocks. He has known the price of one stock for the next N days. He can choose two days, such as Day I, Day J (I<J), to make money.
So if the price of Day I is no more than the price of Day J, then his income is C*(J-I+1) where C is a constant, or his income is 0 instead.
Now he wants to make his income maximum. Can you help him?
The first line, an integer T, indicates the number of test cases (T<=10). For each test case:
The first part: two integers N, C, indicating the number of days and the constant respectively.
The second part: N integer numbers, indicting the stock price of next N days. Each of them is no more than 1000000
2<=N<=100000 1<=C<=100.
Output his maximum income for each test.
Sample Input
5 1
1 2 3 4 5
4 2
1 4 3 2
Sample Output
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.7ms with 1 query(s).