#include "tickets.h" #include <vector> #include <algorithm> #define ll long long #define For(i, n) for(int i = 0; i < n; i++) #define NEK 1000000000 #define vec vector #define pii pair<int, int> using namespace std; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); if(m == 1){ vec<int> a; For(i, n){ a.push_back(x[i][0]); } sort(a.begin(), a.end()); ll sum = 0; vec<vec<int>> odp(n, vec<int>(1, 0)); For(i, n/2){ sum -= a[i]; sum += a[i+n/2]; } allocate_tickets(odp); return sum; } vec<pii> s; ll sum = 0; vec<int> bt, bt2; vec<vec<int>> odp(n, vec<int>(m,-1)); For(i, n){ int mi = 0, ma = 0; For(j, x[i].size()){ if(x[i][j] < x[i][mi]){ mi = j; } if(x[i][j] > x[i][ma]){ ma = j; } } odp[i][ma] = 0; bt.push_back(ma); bt2.push_back(mi); s.push_back({x[i][mi] + x[i][ma], i}); sum += x[i][ma]; } sort(s.begin(), s.end()); For(i, n/2){ odp[s[i].second][bt[s[i].second]] = -1; odp[s[i].second][bt2[s[i].second]] = 0; sum -= s[i].first; } allocate_tickets(odp); return sum; }