#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
ll find_maximum(int k, vector<vi> x) {
int n = (int)x.size();
int m = (int)x[0].size();
// vector<vi> S = x;
// for(int i = 0; i < n; ++i)
// for(int j = 1; j < m; ++j) {
// S[i][j] += S[i][j - 1];
// }
vi A(n, 0);
priority_queue<ii> PQ;
auto calc = [&](int lin, int a) {
return x[lin].end()[-a - 1] + x[lin][k - a - 1];
};
for(int i = 0; i < n; ++i) {
PQ.push({calc(i, A[i]), i});
}
ll sum = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < k; ++j)
sum -= x[i][j];
}
for(int i = 0; i < n * k / 2; ++i) {
auto [val, id] = PQ.top();
PQ.pop();
sum += val;
++A[id];
if(A[id] < k) PQ.push({calc(i, A[i]), i});
}
vector<vi> Re(n, vi(m, -1));
vector<vi> Poz(n), Neg(n);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < k - A[i]; ++j) Neg[i].push_back(j);
for(int j = 0; j < A[i]; ++j) Poz[i].push_back(m - 1 - j);
}
for(int nr = 0; nr < k; ++nr) {
vi ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](auto a, auto b) {
return abs((int)Poz[a].size() - (int)Neg[a].size()) >
abs((int)Poz[b].size() - (int)Neg[b].size());
});
int nr_plus = n / 2, nr_minus = n / 2;
auto assign = [&](int lin, int sgn) {
int u;
if(sgn == 1) {
u = Poz[lin].back();
Poz[lin].pop_back();
--nr_plus;
} else {
u = Neg[lin].back();
Neg[lin].pop_back();
--nr_minus;
}
Re[lin][u] = nr;
};
for(auto it : ord) {
if(!nr_plus) {
assign(it, -1);
} else if(!nr_minus) {
assign(it, 1);
} else {
if(Poz[it].size() > Neg[it].size()) assign(it, 1);
else assign(it, -1);
}
}
}
allocate_tickets(Re);
return sum;
}
