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

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

Nội dung bài viết

1. Đề bài PTIT016D spoj
2. Code tham khảo PTIT016D spoj PTIT- ACM PTIT 2016

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;
}

#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;

}

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

1. Đề bài PTIT016D spoj

Input

Output

Example

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

Bài viết liên quan

Trả lời Hủy