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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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

Email 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 *