#include "tickets.h" #include <vector> #include <algorithm> using namespace std; int n, m; vector< vector<int> > X; long long find_maximum(int k, vector< vector<int> > x) { n = x.size(); m = x[0].size(); X = x; vector<int> ind(n); for(int i = 0; i < n; i++) ind[i] = i; sort(ind.begin(), ind.end(), [] (int p, int q) { return (X[p][0] + X[p][m-1]) < (X[p][0] + X[p][m-1]); }); long long res = 0; vector< vector<int> > s(n, vector<int>(m, -1)); for(int i = 0; i < n/2; i++) { s[ind[i]][0] = 0; res -= X[ind[i]][0]; } for(int i = n/2; i < n; i++) { s[ind[i]][m-1] = 0; res += X[ind[i]][m-1]; } allocate_tickets(s); return res; }