1471C - Strange Birthday Party

Assign people with higher default cost, $k_i$, to the presents with lower cost.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.


using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll solve(vi k, vi c)
{
    sort(begin(k), end(k), greater<int>());
    int cur = 0;
    ll ans = 0;
    for (auto &ki : k)
    {
        if (cur < ki)
            ki = cur++;
        ans += c[ki];
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vi k(n), c(m);
        for (auto &ki : k)
            cin >> ki, ki--;
        for (auto &ci : c)
            cin >> ci;
        cout << solve(k, c) << endl;
    }
    return 0;
}