#include <bits/stdc++.h> #include "tickets.h" using namespace std; long long find_maximum(int k, vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<std::vector<int>> answer; vector <vector<int>> st(n,vector<int>(m,0)); long long ans = 0; for (int i = 0; i < n; i++) { std::vector<int> row(m); for (int j = 0; j < m; j++) { if (j < k) { row[j] = -1; } else { row[j] = -1; } } answer.push_back(row); } int l[n]; int r[n]; auto get = [&](int i) { if (l[i] < 0) return -INT_MAX; return x[i][r[i]] + x[i][l[i]]; }; auto cmp = [&](int a, int b) { return get(a) > get(b); }; priority_queue<int, vector<int>, decltype(cmp)> q(cmp); for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { st[i][j] = -1; } l[i] = k-1; r[i] = m-1; q.push(i); } for (int t = 0; t < k*n/2; t++) { int i = q.top(); q.pop(); st[i][l[i]] = 0; st[i][r[i]] = 1; l[i]--; r[i]--; q.push(i); } vector <vector<int>> mn(n),pl(n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ans += st[i][j] * x[i][j]; if (st[i][j] == 1) { pl[i].push_back(j); } if (st[i][j] == -1) { mn[i].push_back(j); } } } for (int i = 0; i < k; i++) { vector <int> idx(n); iota(idx.begin(),idx.end(),0); sort(idx.begin(),idx.end(),[&](int a, int b){ return pl[a].size() > pl[b].size(); }); for (int j = 0; j < n; j++) { int cur = idx[j]; if (j < n/2) { answer[cur][pl[cur].back()] = i; pl[cur].pop_back(); } else { answer[cur][mn[cur].back()] = i; mn[cur].pop_back(); } } } allocate_tickets(answer); return ans; }