Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DHEXP - Biểu thức

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/dhexp


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ả (-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 (-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 (-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 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

Ghi chú:
  • Có 50% số test ứng với 50% số điểm có n ≤ 105k = 1;
  • Có 50% số test còn lại ứng với 50% số điểm có n ≤ 105;

Được gửi lên bởi:VOJ Team
Ngày:2015-04-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Duyen hai 2015 khoi 10

hide comments
2021-05-27 18:00:56
Tham khảo: https://vnspoj.github.io/problems/DHEXP
2018-08-25 16:06:57
sort(2,n) not sort(1,n)

Last edit: 2018-08-25 16:07:22
2017-12-04 16:39:29
1 đấm AC
2017-08-19 07:55:27 Con Bò Huyền Thoại
https://kienthuc24h.com/dhexp-spoj-bieu-thuc/
2017-06-05 11:43:40
Chú ý số đầu luôn dương :))
2017-05-02 03:44:39
sao mình quicksorf mà có 3.33 nhể
=.=


Last edit: 2017-05-02 03:45:15
2016-10-07 17:35:00 Nguyễn Mai Phương
khó thế không biết. bài này phải quy về đồ thị. để dùng sx topo thành DAG xong quy hoạch động trên cây. :v
2016-07-02 05:50:07 Trần Bảo Huy
kết quả int64 nha :D, longint 50d, qword 76.67
2016-03-29 10:40:04
dd

2016-03-24 09:46:09
co ai lam bai linkgame chua
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.