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

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274811/problem/M

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
2016-01-02 18:50:00 Sơn Tùng M-TP
C++ không được 100 theo mình nghĩ là do dùng cin>>, cout<< nên nó chậm.
Mà sao Python chạy chậm thế nhỉ?
Thuật toán vậy mà C++ lại AC và Python có 36đ à
2015-12-21 14:08:10 ptt
nếu n=10^6, k=n-1 và mỗi phần tử đều mang giá trị 10^6 thì đáp án chả nhẽ ko int64
2015-10-20 17:22:08
nh?t coaye.......http://codepaste.net/43rfq6
2015-08-12 12:14:38 ChienTran
đọc comment bác Brain và đã AC :3
Dm đề bảo 10^6 mà phải int64, phải nộp 4 lần mới AC :(
2015-08-08 09:56:14
THAM KHẢO TẠI https://traitaodo.wordpress.com/2015/08/08/bieu-thuc-dhexp/

Last edit: 2015-09-13 04:54:50
2015-07-30 16:17:17 Lê Thanh Phú
Ban nao co the xem gium xem vi sao 0d vay
http://ideone.com/06kUx3
2015-07-30 16:07:13 Lê Thanh Phú
Quicksort + Tham lam = 0 diem
Ban nao giai thich Test gium voi duoc khong?
AC nhung van 0d
2015-05-27 13:22:12 nguyenngocanh
nếu mà k AC thì để int64 nhá
2015-05-14 18:33:03 Hacking to the Gate
Sao std::sort() trong C++ được có 70 vậy, code bằng Pascal thì được 100. :v
2015-05-04 05:23:35 BRAIN
Chú ý phần tử đầu tiên luôn mang dấu cộng :| nếu sort thì chỉ qsort từ 2 -> n rồi tham lam
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.