#include "tickets.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#include <iostream>
#include <numeric>
using namespace std;
#define F first
#define S second
#define PB push_back
using ll = long long;
// each vector<int> in x is sorted
long long find_maximum(int k, vector<vector<int>> x) {
/* sample interaction
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++) {
if (j < k) {
row[j] = j;
} else {
row[j] = -1;
}
}
answer.push_back(row);
}
allocate_tickets(answer);
return 1;
*/
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
ll sum = 0;
struct Info {
int val;
int i, j, k;
bool operator<(const Info &rhs) const {
return make_pair(val, j) < make_pair(rhs.val, rhs.j);
}
};
priority_queue<Info> pq;
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
answer[i][j] = -2; // lower half
int jj = m-k+j;
sum -= x[i][j];
pq.push({x[i][j]+x[i][jj], i, j, jj});
}
}
for(int i = 0; i < k*n/2; i++) {
answer[pq.top().i][pq.top().j] = -1;
answer[pq.top().i][pq.top().k] = -3; // upper half
sum += pq.top().val;
pq.pop();
}
vector<vector<int>> lo(n), up(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(answer[i][j] == -2) {
lo[i].PB(j);
}
else if(answer[i][j] == -3) {
up[i].PB(j);
}
}
}
priority_queue<pair<int, int>> another_pq;
for(int i = 0; i < n; i++) {
another_pq.push({count(answer[i].begin(), answer[i].end(), -2), i});
}
for(int q = 0; q < k; q++) {
priority_queue<pair<int, int>> new_another_pq;
for(int o = 0; o < n/2; o++) {
int cnt = another_pq.top().F;
int i = another_pq.top().S;
another_pq.pop();
answer[i][lo[i].back()] = q;
lo[i].pop_back();
cnt--;
new_another_pq.push({cnt, i});
}
for(int o = 0; o < n/2; o++) {
int cnt = another_pq.top().F;
int i = another_pq.top().S;
another_pq.pop();
answer[i][up[i].back()] = q;
up[i].pop_back();
new_another_pq.push({cnt, i});
}
another_pq = new_another_pq;
}
allocate_tickets(answer);
return sum;
}
