UTS Open '24 P2 - Happy Gifts

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5typedef long long ll;
    6 
    7int main(){
    8    ios::sync_with_stdio(0);
    9    cin.tie(0);
    10    int n, k;
    11    cin >> n >> k;
    12    vector<int> positive, negative;
    13    for(int i = 0; i < n; i++){
    14        int val; 
    15        cin >> val;
    16        if(val < 0) negative.push_back(-val);
    17        else positive.push_back(val);
    18    }
    19    vector<ll> psa(positive.size() + 1);
    20    sort(positive.begin(), positive.end(), greater<int>());
    21    sort(negative.begin(), negative.end(), greater<int>());
    22    int size = positive.size();
    23    for(int i = 1; i <= size; i++){
    24        psa[i] = psa[i - 1] + positive[i - 1];
    25    }
    26    ll ans = psa[min(k, size)];
    27    ll negative_sum = 0;
    28    for(int i = 0; i < negative.size() && k >= 2; i++){
    29        negative_sum += negative[i];
    30        k -= 2;
    31        ans = max(ans, negative_sum + psa[min(k, size)]);
    32    }  
    33    cout << ans <<'\n';
    34    return 0;
    35}