#include "tickets.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
ll n, k, m;
vector<ll>mns, mxs, mns_, mxs_;
ll dp[1507][1507];
ll cnt0[1507];
vector<pair<int, int>>d;
vector<int>os[1507], ls[1507];
int os_[1507], ls_[1507];
vector<vector<int>>ans;
bool give_zero(int i, int r);
bool give_one(int i, int r) {
if (ls_[i] == ls[i].size()) {
give_zero(i, r);
return false;
}
ans[i][ls[i][ls_[i]]] = r;
ls_[i]++;
return true;
}
bool give_zero(int i, int r) {
if (os_[i] == os[i].size()) {
give_one(i, r);
return false;
}
cnt0[i]--;
ans[i][os[i][os_[i]]] = r;
os_[i]++;
return true;
}
ll find_answer(vector<ll>a) {
ll ans = INF;
for (int i = 0; i < a.size(); i++) {
ll cur = 0;
for (int j = 0; j < a.size(); j++) {
cur += abs(a[i] - a[j]);
}
ans = min(ans, cur);
}
return ans;
}
ll find_maximum(int k, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
if (m == 1) {
vector<ll>v;
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(1, 0);
v.push_back(x[i][0]);
}
allocate_tickets(ans);
return find_answer(v);
}
if (k == 1) {
mns.push_back(0);
mxs.push_back(0);
for (int i = 0; i < n; i++) {
ll mn = INF, mx = 0;
int mn_ = -1, mx_ = -1;
for (int j = 0; j < m; j++) {
if (x[i][j] < mn) {
mn_ = j;
}
if (x[i][j] > mx) {
mx_ = j;
}
mn = min(mn, x[i][j] * 1ll);
mx = max(mx, x[i][j] * 1ll);
}
mns.push_back(mn);
mxs.push_back(mx);
mns_.push_back(mn_);
mxs_.push_back(mx_);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (j != 0 && j != i) {
dp[i][j] = max(dp[i - 1][j] + mxs[i], dp[i - 1][j - 1] - mns[i]);
}
else if (j == 0) {
dp[i][j] = dp[i - 1][j] + mxs[i];
}
else {
dp[i][j] = dp[i - 1][j - 1] - mns[i];
}
}
}
string s = "";
int j = n / 2;
for (int i = n; i > 0; i--) {
if (j == i || (j != 0 && dp[i - 1][j - 1] - mns[i] == dp[i][j])) {
s += '0';
j--;
}
else {
s += '1';
}
}
reverse(s.begin(), s.end());
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
for (int i = 0; i < n; i++) {
if (s[i] == '0') {
ans[i][mns_[i]] = 0;
}
else {
ans[i][mxs_[i]] = 0;
}
}
allocate_tickets(ans);
return dp[n][n / 2];
}
else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cnt0[i] += (x[i][j] == 0);
if (x[i][j] == 0) {
os[i].push_back(j);
}
else {
ls[i].push_back(j);
}
}
}
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m, -1);
}
ll res = 0;
for (int r = 0; r < k; r++) {
for (int i = 0; i < n; i++) {
d.push_back({ cnt0[i],i });
}
sort(d.begin(), d.end());
/*for (auto x : d) {
cout << x.ff << " " << x.ss << " ";
}
cout << endl;*/
ll cnt = 0;
for (int i = 0; i < n / 2; i++) {
cnt += give_one(d[i].ss, r);
}
for (int i = n / 2; i < n; i++) {
cnt += !give_zero(d[i].ss, r);
}
res += min(cnt, n - cnt);
//cout << res << " ";
d.clear();
}
allocate_tickets(ans);
return res;
}
}
/*
3 1 1 1 2 3
4 4 3 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1
5
*/
