[C++] BOJ 25405: Level Up

26 February 2026

Given an integer sequence with length $$N$$ , repeat the following operation $$M$$ times:

Increase the value of $$K$$ smallest elements by $$1$$

The problem is to output the resulting sequence.

In total $M \times K$ is added to the original sequence, and each element can be increased by at most $$1$$ per operation, so a single element can be increased at most $$M$$ times.

Let us find an upper bound $$T$$ . Our goal is to raise the number up to $$T$$ .

However, each element can have at most $$M$$ added to it, Therefore, the cost required to raise one element to $$T$$ (or to $L_{i} + M$ if $L_{i} + M < T$ ) is $\min\left(M, \max\left(0, T - L_{i}\right)\right)$ .

If sum of these costs does not exceed $M \times K$ , then we can use $$T$$ as the upper bound of the numbers.

Using binary search, we can find $$T$$ in $\mathcal{O}(N \log{N})$ time.

After finding $$T$$ , update the sequence $$L$$ accordingly, and distribute the remaining amount appropriately among the elements satisfying $L_{i} = T$ .

c++

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using lll = __int128_t;
using ulll = __uint128_t;

const int INF = 1'000'000'007;
const ll LINF = 1'000'000'000'000'000'007;

int N, K;
vector <ll> L;
ll M;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    L.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> L[i];
    }
    
    cin >> M >> K;

    sort(all(L));

    auto f = [&](ll mid) -> unsigned char {
        ll tot = 0;
        for(int i = 0; i < N; i++) {
            tot += min(M, max(0LL, mid - L[i]));
        }
        return (tot <= M * K ? 1 : 0);
    };

    ll s = 0, e = LINF;
    ll ans = 0;
    while(s <= e) {
        ll mid = (s + e) >> 1;
        if(f(mid) == 1) {
            s = mid + 1;
            ans = mid;
        }
        else {
            e = mid - 1;
        }
    }

    ll use = M * K;
    for(int i = 0; i < N; i++) {
        ll to_use = min(M, max(0LL, ans - L[i]));
        L[i] += to_use;
        use -= to_use;
    }

    for(int i = 0; i < N && use > 0; i++) {
        if(L[i] == ans) L[i]++, use--;
    }

    sort(all(L));
    for(ll &x : L) cout << x << " ";
    cout << endl;
    return 0;
}