Biểu thức
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Một dãy gồm \(n\) số nguyên không âm \(a_1, a_2,..., a_n\) đượ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,..., a_n\) 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,..., a_n\) (a_n ≤ 10^6)
Output
- Một số nguyên là giá trị của biểu thức đạt được.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n ≤ 10^5\) và \(k = 1\);
- Subtask \(2\) (\(50\%\) số điểm): \(n ≤ 10^5\);
Example
Test 1
Input
5 2
28 9 5 1 69 Output
100
Bình luận
Đề bảo số nguyên không âm mà test toàn số âm thế ạ ?? =))
._. cuộc sống đó bạn, chả có rì công = cả :v
chính xác