DHEXP - Biểu thức

Xem PDF

Điểm: 200 (p) Thời gian: 1.1s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một dãy gồm \(n\) số nguyên \(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\)\(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 \(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 \(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.

Ví dụ

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 ≤ 10^5\)\(k = 1\);
  • Có 50% số test còn lại ứng với 50% số điểm có \(n ≤ 10^5\);

Bình luận

Sắp xếp theo
Tải bình luận...

Không có bình luận nào.