Biểu thức

View as PDF

Submit solution


Points: 0.29 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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_i \leq 10^{6})~

Output

Một số nguyên là giá trị của biểu thức đạt được.

Giới hạn

  • Có ~50\%~ số test ứng với ~50\%~ số điểm có ~n \leq 10^{5}~ và ~k = 1~;
  • Có ~50\%~ số test còn lại ứng với ~50\%~ số điểm có ~n \leq 10^{5}~;

Sample Input

5 2
28 9 5 1 69

Sample Output

100

Comments

Please read the guidelines before commenting.


There are no comments at the moment.