======================================
Một dãy gồm n số
nguyên không âm a1, a2,..., an được
viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy
có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu
cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng đó để nhận
được một biểu thức có giá trị lớn nhất.
Ví dụ, với dãy gồm 5 số
nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1+69 là
biểu thức có giá trị lớn nhất.
Yêu cầu: Cho
dãy gồm n số nguyên không âm a1, a2,..., an và
số nguyên dương k, hãy tìm cách đặt k dấu cộng và
(n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được một
biểu thức có giá trị lớn nhất.
Input
-
Dòng đầu chứa hai số nguyên dương n, k (k < n);
-
Dòng thứ hai chứa n số nguyên không âm a1, a2,..., an (an ≤
106)
Output
Một số nguyên là giá trị
của biểu thức đạt được.
Example
Input:
5 2
28 9 5 1 69
Output:
100
=====================
Hướng dẫn:
Bài này cần sort lại mảng A giảm dần từ phần tử 2 tới N.......(Vì phần tử thứ nhất không cần đặt dấu)
Ta sẽ đặt K dấu cộng cho K số đầu tiên kể từ phần tử thứ 2..........rồi tính giá trị biểu thức......xong
