Cold Vote#11772

Cold Vote (Editorial)

Problem Author:	Oleksandr Tymkovych
Prepared by:	Oleksandr Tymkovych
Editorial by:	Denysov Kostiantyn

$Claim 1$ . It is possible to prevent every student from being expelled if and only if $\sum_{i = 1}^{n} s_{i} \geq n \cdot m$ \sum_{i=1}^n {s_i} \ge n \cdot m.

Necessity is simple as with every vote the $\sum_{i = 1}^{n} s_{i}$ \sum_{i=1}^n {s_i} decreases by $1$ and if no one expelled then after rearranging votes, all student statuses are non-negative and then the $\sum_{i = 1}^{n} s_{i} - n \cdot m \geq 0$ \sum_{i=1}^n {s_i} - n \cdot m \ge 0.

Let $f_{i}$ f_i — be statuses of students after all the votes.

For sufficiency, we need to prove that it is possible to rearrange the votes so that all $f_{i} \geq 0$ f_i \ge 0 if $\sum_{i = 1}^{n} f_{i} \geq 0$ \sum_{i=1}^n {f_i} \ge 0. Let's divide $f_{i}$ f_i in two types: positive ( $f_{i} \geq 0$ f_i \ge 0) and negative ( $f_{i} < 0$ f_i<0). From our condition, we have $\sum_{f_{i} \geq 0} f_{i} \geq - \sum_{f_{i} < 0} f_{i}$ \sum_{f_i \ge 0} {f_i} \ge -\sum_{f_i < 0} {f_i}. To increase $f_{i} < 0$ f_i<0 by $1$ we can change the vote to decrease the status of person $i$ to some person with positive status (from that inequality it always exists). This way, by increasing negative $f_{i}$ f_i by one we can make them all positive.

From sufficiency, we can also understand how to get minimal cost. When you increase negative $f_{i}$ f_i you just take the minimal cost of changing among those values who voted for person $i$ .

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    vector<vector<int>> V(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> V[i][j];
            s[V[i][j]]--;
        }
    }
    vector<vector<int>> G(n + 1); 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int C;
            cin >> C;
            G[V[i][j]].push_back(C);
        }
    }
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end(), greater<>());
    }
    set<pair<int, int>> st;
    for (int i = 1; i <= n; i++) {
        st.insert({s[i], i});
    }
    auto upd = [&st](auto it, int delta) {
        auto [status, id] = *it;
        st.erase({status, id});
        st.insert({status + delta, id});
    };
    long long ans = 0;
    while (st.begin()->first < 0) {
        auto [status, id] = *st.begin();
        if (G[id].empty()) {
            cout << "-1\n";
            return 0;
        }
        ans += G[id].back();
        G[id].pop_back();
        upd(st.begin(), 1);
        upd(--st.end(), -1);
    }
    cout << ans << "\n";
}

C++