1799F - Halve or Subtract - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define pii pair<int, int>

const long long inf = 1e18;

const int maxN = 1e6 + 10;
int a[maxN];
string s;
int n, b;
int k1, k2;

void solve() {
    cin >> n >> b >> k1 >> k2;

    for (int i = 1; i<=n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    
    long long ans = inf;
    for (int i = 0; i<=min(k1, k2); i++) {

        long long curAns = 0;
        vector<int> difs;

        for (int j = 1; j <= i; j++) {
            curAns += max(0, (a[j] + 1) / 2 - b);
        }
        
        int ostalo = min(n - i, k1 + k2 - 2*i);

        for (int j = i + 1; j<= i + ostalo; j++) {
            curAns+= (a[j] + 1) / 2;
            difs.pb(a[j] - (a[j] + 1)/2 - min(b, a[j]));
        }

        sort(difs.begin(), difs.end());
        for (int l = 0; l < k2 - i; l++) {
            if (difs[l] > 0 && ostalo - l <= k1 - i) break;
            curAns+=difs[l];
        }
        for (int j = i + ostalo + 1;  j<= n; j++) curAns += a[j];
        ans = min(ans, curAns);
    }

    cout << ans << endl;
}

int main() {

    int tc;

    cin >> tc;

    while(tc--) {
        solve();
    }
    
    return 0;
}