#include "tickets.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1510;
const ll inf=1e14;
int ma[maxn], me[maxn], id_me[maxn], id_ma[maxn];
int v[maxn][maxn];
ll dp[maxn][maxn];
vector<int>grande[maxn], pequeno[maxn];
ll solve2(int n, int m){
vector<vector<int>>ans(n,vector<int>(m,-1));
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) dp[i][j]=-inf;
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
int k=i-j;
if(j) dp[j][k]=max(dp[j][k],dp[j-1][k]-me[i]);
if(k) dp[j][k]=max(dp[j][k],dp[j][k-1]+ma[i]);
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=n;j++) cout << dp[i][j] << " ";
// cout << endl;
// }
int a=n/2, b=n/2;
while(a+b){
if(!a){ // tenho q pegar o maior
ans[a+b-1][m-1]=0;
b--;
}else if(!b){ // tenho q pegar o menor
ans[a+b-1][0]=0;
a--;
}else if(dp[a-1][b]-me[a+b]==dp[a][b]){
ans[a+b-1][0]=0;
a--;
}else{
ans[a+b-1][m-1]=0;
b--;
}
}
allocate_tickets(ans);
return dp[n/2][n/2];
}
ll solve4(int n, int m, int k){
vector<vector<int>>ans(n,vector<int>(m,-1));
vector<pair<int,pair<int,int>>>process;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) process.push_back({v[i][j],{i-1,j-1}});
sort(process.begin(),process.end());
int tot=n*m;
ll resp=0;
for(int i=0;i<(int)process.size();i++){
pair<int,int>p=process[i].second;
if(i>=tot/2){
grande[p.first].push_back(p.second);
resp+=process[i].first;
}else{
pequeno[p.first].push_back(p.second);
resp-=process[i].first;
}
}
for(int i=0;i<k;i++){
vector<pair<int,int>>big;
for(int j=0;j<n;j++) big.push_back({grande[j].size(),j});
sort(big.begin(),big.end()); reverse(big.begin(),big.end());
for(int j=0;j<n;j++){
int id=big[j].second;
if(j>=n/2){
ans[id][pequeno[id].back()]=i;
pequeno[id].pop_back();
}else{
ans[id][grande[id].back()]=i;
grande[id].pop_back();
}
}
}
allocate_tickets(ans);
return resp;
}
ll find_maximum(int k, vector<vector<int>> x) {
int n=x.size(), m=x[0].size();
for(int i=1;i<=n;i++){
me[i]=x[i-1][0];
ma[i]=x[i-1][m-1];
for(int j=1;j<=m;j++) v[i][j]=x[i-1][j-1];
}
if(k==1) return solve2(n,m);
else if(k==m) return solve4(n,m,k);
else{
vector<vector<int>>ans(n,vector<int>(m,-1));
ll resp=0;
for(int r=0;r<k;r++){
memset(me,-1,sizeof(me));
memset(ma,-1,sizeof(ma));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) if(me[i+1]==-1&&ans[i][j]==-1) me[i+1]=x[i][j], id_me[i]=j;
for(int i=0;i<n;i++)
for(int j=m-1;j>=0;j--) if(ma[i+1]==-1&&ans[i][j]==-1) ma[i+1]=x[i][j], id_ma[i]=j;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) dp[i][j]=-inf;
dp[0][0]=0;
for(int i=1;i<=n;i++){
//cout << "+- " << me[i] << " " << ma[i] << endl;
for(int j=0;j<=n;j++){
int k=i-j;
if(j) dp[j][k]=max(dp[j][k],dp[j-1][k]-me[i]);
if(k) dp[j][k]=max(dp[j][k],dp[j][k-1]+ma[i]);
}
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=n;j++) cout << dp[i][j] << " ";
// cout << endl;
// }
int a=n/2, b=n/2;
while(a+b){
if(!a){ // tenho q pegar o maior
ans[a+b-1][id_ma[a+b-1]]=r;
b--;
}else if(!b){ // tenho q pegar o menor
ans[a+b-1][id_me[a+b-1]]=r;
a--;
}else if(dp[a-1][b]-me[a+b]==dp[a][b]){
ans[a+b-1][id_me[a+b-1]]=r;
a--;
}else{
ans[a+b-1][id_ma[a+b-1]]=r;
b--;
}
}
resp+=dp[n/2][n/2];
//cout << "! " << dp[n/2][n/2] << endl;
}
allocate_tickets(ans);
return resp;
}
}
