Tickets

Solution Approach

Key Observation

Since $n$ is even, the prize for a round with sorted values $v_0 \le v_1 \le \cdots \le v_{n-1}$ is: \[ \text{prize} = \sum_{i=n/2}^{n-1} v_i - \sum_{i=0}^{n/2-1} v_i \]

So we want to maximize the total prize. Each color contributes $k$ tickets across rounds: some are ``positive'' (among the top $n/2$ in their round, contributing $+v$) and some are ``negative'' (among the bottom $n/2$, contributing $-v$).

For each color, exactly $k$ tickets are used. Among these $k$ tickets, some number $p_i$ are positive and $k - p_i$ are negative. The constraint is $\sum_i p_i = k \cdot n/2$ (each round needs exactly $n/2$ positive tickets).

Greedy Strategy

To maximize total prize:

• For positive contributions, use the largest tickets: tickets $x[i][m-1], x[i][m-2], \ldots, x[i][m-p_i]$.

• For negative contributions, use the smallest tickets: tickets $x[i][0], x[i][1], \ldots, x[i][k-p_i-1]$.

• Total contribution of color $i$: $\sum_{j=0}^{k-p_i-1} (-x[i][j]) + \sum_{j=m-p_i}^{m-1} x[i][j]$.

Optimal $p_i$ Values

Start with $p_i = 0$ for all $i$ (all negative). Then greedily increase $p_i$ values to maximize marginal gain. Increasing $p_i$ from $t$ to $t+1$: gain = $x[i][m-t-1] + x[i][k-t-1]$ (add a large positive and remove a small negative). Use a priority queue to select the best increments until $\sum p_i = k \cdot n/2$.

C++ Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long find_maximum(int k, vector<vector<int>> x) {
    int n = x.size(), m = x[0].size();
    int half = n / 2;

    // p[i] = number of "positive" uses for color i
    vector<int> p(n, 0);
    // Initially all p[i] = 0: all k tickets used negatively
    // Marginal gain of incrementing p[i] from t to t+1:
    //   gain = x[i][m - t - 1] + x[i][k - 1 - t]
    //   (add top ticket as positive, remove bottom ticket from negative)

    // Priority queue: (gain, color_index)
    priority_queue<pair<ll, int>> pq;
    for (int i = 0; i < n; i++) {
        ll gain = (ll)x[i][m - 1] + x[i][k - 1];
        pq.push({gain, i});
    }

    int total_positive = k * half;
    ll total_prize = 0;

    // Initial total with all negative:
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            total_prize -= x[i][j];

    while (total_positive > 0) {
        auto [gain, i] = pq.top(); pq.pop();
        total_prize += gain;
        p[i]++;
        total_positive--;

        if (p[i] < k) {
            int t = p[i];
            ll new_gain = (ll)x[i][m - t - 1] + x[i][k - 1 - t];
            pq.push({new_gain, i});
        }
    }

    // Now assign tickets to rounds
    // For color i: positive tickets are x[i][m-p[i]], ..., x[i][m-1]
    //              negative tickets are x[i][0], ..., x[i][k-p[i]-1]

    // Build the allocation matrix s[i][j] = round number or -1
    vector<vector<int>> s(n, vector<int>(m, -1));

    // Assign rounds: each round needs exactly n/2 positive and n/2 negative
    // Collect (color, ticket_index, is_positive) and assign to rounds

    // Simple assignment: sort colors by p[i], assign positive tickets round by round
    // Use a greedy matching.

    // For each color, create a list of (round assignments)
    // Positive tickets: assign to rounds 0..p[i]-1 (will fix later)
    // Negative tickets: assign to rounds p[i]..k-1

    // Actually, we need each round to have exactly n/2 positive colors.
    // This is a bipartite matching problem, but can be solved greedily.

    // Create a list of (color, round_index) for positive assignments
    // Each color i has p[i] positive assignments.

    // Use a round-robin approach:
    vector<vector<int>> pos_rounds(n), neg_rounds(n);

    // Assign positive rounds: distribute using priority queue
    // Each round needs exactly half colors as positive
    vector<int> pos_count(k, 0);
    vector<pair<int,int>> color_order; // (p[i], i) sorted descending
    for (int i = 0; i < n; i++)
        color_order.push_back({p[i], i});
    sort(color_order.rbegin(), color_order.rend());

    // Greedy: for each color (in order of most positive), assign to rounds with fewest positive
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> round_pq;
    for (int r = 0; r < k; r++) round_pq.push({0, r});

    for (auto [pi, i] : color_order) {
        vector<pair<int,int>> tmp;
        for (int t = 0; t < pi; t++) {
            auto [cnt, r] = round_pq.top(); round_pq.pop();
            pos_rounds[i].push_back(r);
            tmp.push_back({cnt + 1, r});
        }
        for (auto& pr : tmp) round_pq.push(pr);
    }

    // Assign negative rounds: remaining rounds for each color
    for (int i = 0; i < n; i++) {
        set<int> pos_set(pos_rounds[i].begin(), pos_rounds[i].end());
        for (int r = 0; r < k; r++)
            if (!pos_set.count(r))
                neg_rounds[i].push_back(r);
    }

    // Fill allocation
    for (int i = 0; i < n; i++) {
        // Positive: largest tickets -> sort positive rounds doesn't matter
        sort(pos_rounds[i].begin(), pos_rounds[i].end());
        for (int t = 0; t < p[i]; t++) {
            int ticket = m - p[i] + t;
            int round = pos_rounds[i][t];
            s[i][ticket] = round;
        }
        // Negative: smallest tickets
        sort(neg_rounds[i].begin(), neg_rounds[i].end());
        for (int t = 0; t < k - p[i]; t++) {
            int ticket = t;
            int round = neg_rounds[i][t];
            s[i][ticket] = round;
        }
    }

    // allocate_tickets(s); // IOI grader call
    // For local testing:
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            printf("%d ", s[i][j]);
        printf("\n");
    }

    return total_prize;
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<vector<int>> x(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &x[i][j]);
    printf("%lld\n", find_maximum(k, x));
    return 0;
}

Complexity Analysis

• Time complexity: $O(nk \log(nk))$ for the priority queue operations during greedy selection and round assignment.

• Space complexity: $O(nm)$ for the allocation matrix.