Subprojects#92

Subprojects (Editorial)

We are asked to choose at most $t$ subproject with max total value. Note that he cannot choose any subproject mutiple times.

The solution is to choose top $t$ subprojects with greatest value.

We can show that this greedy solution is not worse than any other solution by a simple Exchange Argument.

Let $G$ be the set of the $t$ highest-value subprojects, and let $O$ be any optimal solution. If $O \neq = G$ O \neq G, then there is some $g \in G ∖ O$ g \in G \setminus O and some $o \in O ∖ G$ o \in O \setminus G. Since $g$ is among the top $t$ values, $v a l u e (g) \geq v a l u e (o)$ value(g) \ge value(o). Replacing $o$ by $g$ does not decrease the total value. Repeating this exchange, we transform $O$ into $G$ without decreasing value. Hence $G$ is optimal.

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int T=1;
    cin >> T;
    for (int tt = 0; tt < T; tt += 1) {
        int t;
        cin >> t;
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a) {
            cin >> x;
        }
        auto it = min(a.end(), a.begin()+t);
        nth_element(a.begin(), it, a.end(), greater<int>());
        cout << accumulate(a.begin(), it, 0ll) << "\n";
    }
}

Time complexity: $O (p)$ for finding kth order statistic or $O (p \cdot l o g p)$ \mathcal{O}(p \cdot log p) for sorting.