#include "tickets.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
#define int long long
using namespace std;
struct Move
{
int id;
int perte;
bool operator<(const Move &autre) const
{
if (perte != autre.perte)
return perte < autre.perte;
return id < autre.id;
}
};
const long long OO = 1e14;
long long find_maximum(signed k, vector<vector<signed>> x)
{
int nCouleurs = sz(x);
int TOTAL = 0;
vector<vector<signed>> ans;
ans.resize(nCouleurs);
for (auto& ligne : ans){
ligne.resize(sz(x[0]));
for (auto& val : ligne)
val = -1;
}
vector<int> left(nCouleurs, 0), right(nCouleurs, sz(x[0]) - 1);
// On suppose k = 1
for (int i = 0; i < k; ++i){
vector<pii> options(nCouleurs);
vector<int> vals;
for (int i = 0; i < nCouleurs; ++i)
{
options[i] = {x[i][left[i]], x[i][right[i]]};
vals.pb(x[i][0]);
vals.pb(x[i][sz(x[0]) - 1]);
}
vector<int> utilises;
int gain = 0;
sort(all(vals));
for (int med : vals) {
vector<Move> moves;
int tot = 0, enDessous = 0;
vector<int> left(nCouleurs, 0);
for (int id = 0; id < nCouleurs; ++id) {
int perte = 0;
tot += abs(med - options[id].x);
enDessous += (options[id].y < med);
if (options[id].y < med)
left[id] = 1;
if (options[id].y < med || options[id].x > med)
perte = OO;
else {
perte = abs(options[id].x - med) - abs(options[id].y - med);
enDessous++;
left[id] = 1;
}
moves.pb({id, perte});
}
//cout << tot << endl;
sort(all(moves));
int i;
for (i = 0; enDessous > nCouleurs/2; ++i, --enDessous){
tot -= moves[i].perte;
left[moves[i].id] = 0;
}
//if (enDessous >= nCouleurs/2)
// continue;
/*
cout << "med" << med << " " << tot << " " << enDessous << endl;
for (int i : left)
cout << i << " ";
cout << endl;*/
if (tot > gain && enDessous == nCouleurs/2){
gain = tot;
utilises = left;
}
}
TOTAL += gain;
for (int ilig = 0; ilig < nCouleurs; ++ilig){
if (utilises[ilig])
ans[ilig][left[ilig]++] = i;
else
ans[ilig][right[ilig]--] = i;
}
}
/* for (int utilise : utilises)
cout << utilise << " ";
cout << endl;
*/
allocate_tickets(ans);
return TOTAL;
}
