Nguồn: http://vn.spoj.com/PTIT
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.
Dữ liệu vào:
+ Dòng đầu
chứa hai số nguyên dương n,
k (k < n ≤ 105);
+ Dòng thứ
hai chứa n số nguyên không âm a1, a2,..., an (an ≤ 106)
Dữ liệu ra:
-
Một số nguyên là giá trị của biểu thức đạt được.
Ví dụ:
|
PTIT016D.INP
|
PTIT016D.OUT
|
|
5 2
28 9
5 1 69
|
100
|
