#include <bits/stdc++.h>
#include "tickets.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 1500 + 5;
void partition(int k, vector<vector<int>> wsign) {
int n = sz(wsign), m = sz(wsign[0]);
vector<pii> freq(n, pii{0, 0});
vector<deque<int>> sorted(n);
vector<vector<signed>> rez(n, vector<signed>(m, -1));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) if(wsign[i][j] == -1) sorted[i].emplace_back(j), freq[i].first++;
for(int j = 0; j < m; j++) if(wsign[i][j] == 1) sorted[i].emplace_back(j), freq[i].second++;
}
for(int Q = 0; Q < k; Q++) {
vector<int> checked(n);
vector<int> atr(n);
iota(all(atr), 0);
sort(all(atr), [&](auto a, auto b) { return freq[a].first > freq[b].first; });
for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) {
int i = atr[T];
if(checked[i]) continue;
if(freq[i].first > 0) {
rez[i][sorted[i].front()] = Q;
sorted[i].pop_front();
cnt++;
checked[i] = 1;
freq[i].first--;
}
}
sort(all(atr), [&](auto a, auto b) { return freq[a].second > freq[b].second; });
for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) {
int i = atr[T];
if(checked[i]) continue;
if(freq[i].second > 0) {
rez[i][sorted[i].back()] = Q;
sorted[i].pop_back();
cnt++;
checked[i] = 1;
freq[i].second--;
}
}
}
allocate_tickets(rez);
return;
}
const int inf = 1e9 + 5;
const ll infll = 1e18 + 5;
struct Flux {
struct Edg {
int other;
ll cost;
int flux, cap;
};
vector<Edg> edg;
vector<vector<int>> g;
vector<int> p;
vector<ll> pot;
vector<ll> dist;
vector<int> inque;
vector<int> f;
//vector<int>
int S, T;
void init(int s, int t, int n) {
g.resize(n);
pot.resize(n);
dist.resize(n);
inque.resize(n);
f.resize(n);
p.resize(n);
S = s;
T = t;
}
int addedg(int u, int v, int c, ll w) {
g[u].emplace_back(sz(edg));
edg.emplace_back(Edg{v, w, 0, c});
g[v].emplace_back(sz(edg));
edg.emplace_back(Edg{u, -w, 0, 0});
return sz(edg) - 2;
}
void SPFA() {
fill(all(dist), infll);
fill(all(inque), 0);
fill(all(f), -1);
queue<int> que;
inque[S] = 1;
dist[S] = 0;
p[S] = -1;
f[S] = inf;
que.emplace(S);
while(!que.empty()) {
auto node = que.front();
que.pop();
inque[node] = 0;
for(auto e : g[node]) {
if(edg[e].flux < edg[e].cap && dist[edg[e].other] > dist[node] + edg[e].cost) {
dist[edg[e].other] = dist[node] + edg[e].cost;
f[edg[e].other] = min(f[node], edg[e].cap - edg[e].flux);
p[edg[e].other] = e;
if(!inque[edg[e].other])
inque[edg[e].other] = 1,
que.emplace(edg[e].other);
}
}
}
return;
}
void dijkstra() {
fill(all(dist), infll);
fill(all(f), -1);
priority_queue<pii, vector<pii>, greater<pii>> heap;
dist[S] = 0;
p[S] = -1;
f[S] = inf;
heap.emplace(0, S);
while(!heap.empty()) {
auto [d, node] = heap.top();
heap.pop();
if(d != dist[node]) continue;
for(auto e : g[node]) {
int d2 = d + edg[e].cost + pot[node] - pot[edg[e].other];
if(edg[e].flux < edg[e].cap && dist[edg[e].other] > d2) {
dist[edg[e].other] = d2;
f[edg[e].other] = min(edg[e].cap - edg[e].flux, f[node]);
p[edg[e].other] = e;
heap.emplace(d2, edg[e].other);
}
}
}
for(int i = 0; i < sz(dist); i++)
dist[i] += pot[i];
return;
}
bool dijk = 0;
void SP() {
if(!dijk) SPFA();
else dijkstra();
dijk = 1;
}
pair<ll,int> flux() {
ll cost = 0;
int flow = 0;
while(true) {
SP();
if(f[T] == -1) break;
flow += f[T];
cost += (ll)f[T] * dist[T];
int current_edg = p[T];
while(current_edg != -1) {
edg[current_edg].flux += f[T];
edg[current_edg ^ 1].flux -= f[T];
current_edg = p[edg[current_edg ^ 1].other];
}
swap(pot, dist);
}
return pii{cost, flow};
}
};
int N, M;
int S() { return 0; }
int T() { return 1; }
int row(int k) { return 2 + k; }
int cellp(int x, int y) { return 2 + N + x * M + y; }
int cellm(int x, int y) { return 2 + N + N * M + x * M + y; }
int Tp() { return 2 + N + N * M + N * M; }
int Tm() { return 2 + N + N * M + N * M + 1; }
ll S2(signed k, vector<vector<signed>> d) {
vector<pii> values;
int n = sz(d), m = sz(d[0]);
N = n;
M = m;
vector<vector<int>> atrp(n, vector<int>(m, 0));
vector<vector<int>> atrm(n, vector<int>(m, 0));
Flux flux;
flux.init(S(), T(), Tm() + 5);
for(int i = 0; i < n; i++) {
flux.addedg(S(), row(i), k, 0);
for(int j = 0; j < m; j++) {
atrp[i][j] = flux.addedg(row(i), cellp(i, j), 1, -d[i][j]);
flux.addedg(cellp(i, j), Tp(), 1, 0);
atrm[i][j] = flux.addedg(row(i), cellm(i, j), 1, d[i][j]);
flux.addedg(cellm(i, j), Tm(), 1, 0);
}
}
flux.addedg(Tm(), T(), n / 2 * k, 0);
flux.addedg(Tp(), T(), n / 2 * k, 0);
auto [sum, f] = flux.flux();
sum *= -1;
vector<int> freq(n);
vector<vector<int>> signs(n, vector<int>(m, 0));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(flux.edg[atrp[i][j]].flux == 1)
signs[i][j] = 1;
if(flux.edg[atrm[i][j]].flux == 1)
signs[i][j] = -1;
}
}
partition(k, signs);
return sum;
}
ll S3(signed k, vector<vector<signed>> d) {
int n = sz(d), m = sz(d[0]);
vector<pii> freq(n, pii{0, 0});
vector<deque<int>> sorted(n);
vector<vector<signed>> rez(n, vector<signed>(m, -1));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) if(d[i][j] == 0) sorted[i].emplace_back(j), freq[i].first++;
for(int j = 0; j < m; j++) if(d[i][j] == 1) sorted[i].emplace_back(j), freq[i].second++;
}
ll sum = 0;
for(int Q = 0; Q < k; Q++) {
vector<int> checked(n);
vector<int> atr(n);
iota(all(atr), 0);
sort(all(atr), [&](auto a, auto b) { return freq[a].first > freq[b].first; });
int total = 0;
for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) {
int i = atr[T];
if(checked[i]) continue;
if(freq[i].first > 0) {
rez[i][sorted[i].front()] = Q;
sorted[i].pop_front();
cnt++;
checked[i] = 1;
freq[i].first--;
}
}
sort(all(atr), [&](auto a, auto b) { return freq[a].second > freq[b].second; });
for(int T = 0, cnt = 0; cnt < n / 2 && T < n; T++) {
int i = atr[T];
if(checked[i]) continue;
if(freq[i].second > 0) {
total++;
rez[i][sorted[i].back()] = Q;
sorted[i].pop_back();
cnt++;
checked[i] = 1;
freq[i].second--;
}
}
for(int T = 0; T < n; T++) {
int i = atr[T];
if(checked[i]) continue;
if(freq[i].second > 0)
total++,
freq[i].second--;
else
freq[i].first--;
rez[i][sorted[i].back()] = Q;
sorted[i].pop_back();
checked[i] = 1;
}
sum += min(total, n - total);
}
allocate_tickets(rez);
return sum;
}
ll S4(signed k, vector<vector<signed>> d) {
vector<pii> values;
int n = sz(d), m = sz(d[0]);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
values.emplace_back(i, j);
sort(all(values), [&](auto a, auto b) { return d[a.first][a.second] < d[b.first][b.second]; });
vector<vector<int>> signs(n, vector<int>(m, 1));
for(int i = 0; i < n / 2 * k; i++)
signs[values[i].first][values[i].second] = -1;
partition(k, signs);
ll sum = 0;
for(auto [a, b] : values) {
sum += d[a][b] * signs[a][b];
}
return sum;
}
ll S1(signed k, vector<vector<signed>> d) {
int n = sz(d), m = 1;
vector<vector<signed>> rez(n, vector<signed>(m, 0));
allocate_tickets(rez);
vector<int> v;
for(auto a : d)
for(auto x : a) v.emplace_back(x);
sort(all(v));
ll sum = 0;
for(int i = 0; i < n; i++)
sum += v[i];
for(int i = 0; i < n / 2; i++)
sum -= 2 * v[i];
return sum;
}
long long find_maximum(signed k, std::vector<std::vector<signed>> d) {
bool ok = 1;
for(auto a : d)
for(auto x : a)
ok &= (x == 0 || x == 1);
if(sz(d[0]) == 1) return S1(k, d);
if(k == sz(d[0]))
return S4(k, d);
if(ok)
return S3(k, d);
else
return S2(k, d);
}
#undef int
/**
Anul asta se da centroid.
-- Surse oficiale
*/
