Link bài gốc : http://vnoi.info/problems/show/DHEXP/
Đề bài :
Một dãy gồm n số nguyên không âm a_1, _a_2,…, 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 _a_1, _a_2,…, 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 a_1, a_2,…, aN _(ai _≤ 10^6)
Output
Một số nguyên là giá trị của biểu thức đạt được.
Ví dụ
Input
5 2
28 9 5 1 69
Output
100
Solution
Tham Khảo Tại : http://dataurbia.com/15oD
Code
Tham Khảo Tại : http://dataurbia.com/15m3