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.|

PTIT016D - ACM PTIT 2016 D - Biểu thức

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ả (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 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 (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 ≤ 105);

-         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

Được gửi lên bởi:Admin
Ngày:2016-04-26
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2017-08-22 19:41:14 Ðặng Minh Tiến
https://kienthuc24h.com/ptit016d-spoj-ptit-acm-ptit-2016-d-bieu-thuc/
2017-02-16 19:41:15
test đb là gì vậy :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.