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

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT016D/

1. Đề bài PTIT016D spoj

Một dãy gồm n số nguyên không âm a₁, a₂,…, 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 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 ≤ 10⁵);

–         Dòng thứ hai chứa n số nguyên không âm a₁, a₂,…, a_n (a_n ≤ 10⁶)

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

2. Code tham khảo PTIT016D spoj PTIT- ACM PTIT 2016

#include <iostream>
#include <algorithm>
#include<functional>

using namespace std;
#define nmax 100000

long long n, k, a[nmax];

void docfile()
{
    cin >> n>> k;
    long i;
    for (i = 0; i < n; i++)
        cin >> a[i];
}

void xuli()
{
    sort(a + 1, a + n, greater<int>());
    long i;
    long long s = 0;
    for (i = 0; i <= k; i++)
        s = s + a[i];
    for (i = k+1; i <n; i++)
        s = s - a[i];
    cout << s;
}

int main()
{
    docfile();
    xuli();
    return 0;
}