Subsequence solution codeforces

Subsequence solution codeforces

Alice has an integer sequence aa of length nn and all elements are different. She will choose a subsequence of aa of length mm, and defines the value of a subsequence ab1,ab2,,abmab1,ab2,…,abm as

i=1m(mabi)i=1mj=1mf(min(bi,bj),max(bi,bj)),∑i=1m(m⋅abi)−∑i=1m∑j=1mf(min(bi,bj),max(bi,bj)),

where f(i,j)f(i,j) denotes min(ai,ai+1,,aj)min(ai,ai+1,…,aj).

Alice wants you to help her to maximize the value of the subsequence she choose.

A sequence ss is a subsequence of a sequence tt if ss can be obtained from tt by deletion of several (possibly, zero or all) elements.

Subsequence solution codeforces

The first line contains two integers nn and mm (1mn40001≤m≤n≤4000).

The second line contains nn distinct integers a1,a2,,ana1,a2,…,an (1ai<2311≤ai<231).

Output

Print the maximal value Alice can get.

Subsequence solution codeforces

input

Copy
6 4
15 2 18 12 13 4
output

Copy
100

Subsequence solution codeforces

Copy
11 5
9 3 7 1 8 12 10 20 15 18 5
output

Copy
176

Subsequence solution codeforces

Copy
1 1
114514
output

Copy
0
input

Copy
2 1
666 888

Subsequence solution codeforces

Copy
0
Note

In the first example, Alice can choose the subsequence [15,2,18,13][15,2,18,13], which has the value 4(15+2+18+13)(15+2+2+2)(2+2+2+2)(2+2+18+12)(2+2+12+13)=1004⋅(15+2+18+13)−(15+2+2+2)−(2+2+2+2)−(2+2+18+12)−(2+2+12+13)=100. On top of that, the subsequence [15,2,18,12][15,2,18,12] is also a possible answer.

In the second example, there are a variety of subsequences with value 176176, and one of them is [9,7,12,20,18][9,7,12,20,18].

Leave a Comment

Your email address will not be published.