/**
* Another problem from tinjyu's training, though we didn't directly go through the
* full solution. The "minimum sum of dist. to a point" is classic; we know that
* point b is the median, i.e. any val in [(n/2)-th_num, #(n/2+1)-th_num]. The obs.
* here is that the actual val we take is irrelevant. Since n is even, the val would
* be cancelled out so the
* prize = #sum_of_the_(n/2)_larger_num - #sum_of_the_(n/2)_smaller_num.
*
* This means in each round, we maximize #sum_of_(n/2)_num - #sum_of_remaining
* because this naturally finds the larger n numbers to minus the n smaller ones
* In k=1, we know that if we wanna find a num to be part of the smaller numbers,
* this num has to be the smallest in its row. Similarly, the largest num in the row
* shall be picked if it's a "larger" element. With some greedy arguments, the n rows
* with a larger #min + #max shall pick its maximum, while the remaining rows/colors
* should pick its minimum.
*
* Sadly, this greedy approach isn't correct for other values of k, but the thing we
* know (and can prove) using our experience with k=1 is:
* Each time a "plus" element is picked, it must be largest value of that
* color. Each time when a "minus" element is picked, it must be the
* smallest value in the row.
* Yep, this is valid, though we don't know what colors should be picked as "plus" or
* "minus" (yet).
*
* I then looked at [S3], which i didn't finish. After this, I went to [S4], i.e.
* k=n. In this scenario, every num in x[][] is either added to or subtracted from
* the final ans. Naturally, we want the largest nm/2 values to be "plus", while the
* nm/2 smallest ones to be "minus". It turns out that we can always give a
* construction that achieves this. Imagine that we've decided which elements are
* "plus" & which ones are "minus"; as long as the num of rows with all "plus" <= n/2
* and num of rows with all "minus" <= n/2, we can always find a round of tickets
* with n/2 "plus" & n/2 "minus". If the contrary happens, either "plus" or "minus"
* elements have a num >nm/2, which is impossible. This means we can always induct
* downwards.
*
* Wow, [S4] is really inspiring. Now, for each row of values a prefix is chosen for
* "minus" and a suffix is chosen for "plus". We can use dp to find exactly nk/2
* "minus" and exactly nk/2 "plus" with maximum profit, and give a construction since
* this is just [S4] with m -> k. Well, at least I thought so, but this results in a
* O((nm)^2) dp (assuming k is close to m). This implies that we can only score 12
* pts in [S5], AND we'll have to code tons more code to score previous subtasks.
* (I admit that this is sth I hate about IOI)
* Define r[i][j] to be the difference in color i when we pick j "plus". In other
* words, r[i][j] = #sum_of_suffix_with_len_j - #sum_of_prefix_with_len_(k-j). It's
* easy to see that r[i][] is increasing, but after carefully examining this, the
* difference between adjacent terms in r[i][] is decreasing. Therefore, we can just
* greedily find the nk/2 "plus". Finally, I've finished this problem!
*
* Time Complexity: O(mn * log(mn))
* Implementation 1 (Full solution, greedy + sorting + construction)
*/
#include <bits/stdc++.h>
#include "tickets.h"
typedef long long ll;
typedef std::vector<int> vec;
struct pair_t {
ll diff;
int color;
int plus; // num of plus
};
ll find_maximum(int k, std::vector<vec> x) {
int n = x.size(), m = x[0].size();
std::vector<pair_t> pairs;
ll price = 0;
for (int i = 0; i < n; i++) {
std::vector<ll> prefix(m + 1);
prefix[0] = 0;
for (int j = 0; j < m; j++)
prefix[j + 1] = prefix[j] + x[i][j];
std::vector<ll> r(k + 1);
for (int j = 0; j <= k; j++)
r[j] = -prefix[k - j] + (prefix[m] - prefix[m - j]);
price += r[0];
for (int j = 1; j <= k; j++) {
assert(r[j] >= r[j - 1]);
pairs.push_back(pair_t{r[j] - r[j - 1], i, j});
}
for (int j = 1; j < k; j++)
assert(r[j] - r[j - 1] >= r[j + 1] - r[j]);
}
std::sort(pairs.begin(), pairs.end(),
[](const pair_t& p1, const pair_t& p2) {
return p1.diff > p2.diff || (p1.diff == p2.diff && p1.plus < p2.plus);
});
vec plus(n, 0);
for (int l = 0; l < n * k / 2; l++)
price += pairs[l].diff, plus[pairs[l].color] = pairs[l].plus;
vec minus(n);
for (int i = 0; i < n; i++) {
minus[i] = k - plus[i];
assert(plus[i] >= 0 && minus[i] >= 0);
}
vec left(n, 0), right(n, m - 1);
std::vector<vec> tickets(n, vec(m, -1));
for (int r = 0; r < k; r++) {
int m_count = 0, p_count = 0;
std::vector<bool> must(n, false); // if i must be minus or must be plus
for (int i = 0; i < n; i++) {
if (plus[i] == 0) {
tickets[i][left[i]] = r, left[i]++;
minus[i]--, m_count++, must[i] = true;
} else if (minus[i] == 0) {
tickets[i][right[i]] = r, right[i]--;
plus[i]--, p_count++, must[i] = true;
}
}
for (int i = 0; i < n; i++) {
if (!must[i]) {
if (m_count < n / 2)
tickets[i][left[i]] = r, left[i]++, m_count++, minus[i]--;
else if (p_count < n / 2)
tickets[i][right[i]] = r, right[i]--, p_count++, plus[i]--;
else
std::abort(); // absurd
}
}
}
allocate_tickets(tickets);
return price;
}
