DHEXP - Biểu thức
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
Ghi chú:
- Có 50% số test ứng với 50% số điểm có n ≤ 105 và k = 1;
- Có 50% số test còn lại ứng với 50% số điểm có n ≤ 105;
Added by: | VOJ Team |
Date: | 2015-04-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | Duyen hai 2015 khoi 10 |