PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016D/

1. Đề bài PTIT016D spoj

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 ≤ 105);

–         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

2. Code tham khảo PTIT016D spoj PTIT- ACM PTIT 2016

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *