#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> #define ff first #define ss second using namespace std; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vec<pair<int, pii>> p; For(i, n){ For(j, m){ p.push_back({x[i][j], {i, j}}); } } sort(p.begin(), p.end()); ll sum = 0; int kolo1 = 0; vec<vec<int>> velkaci(n); vec<vec<int>> odp(n, vec<int>(m, -1)); vec<vec<int>> bol(n, vec<int>(k, 0)); For(i, (n*m)/2){ sum += p[i+(n*m)/2].ff; int ja = p[i+(n*m)/2].ss.ff; int ja_listok = p[i+(n*m)/2].ss.ss; velkaci[ja].push_back({ja_listok}); } For(i, velkaci.size()){ For(j, velkaci[i].size()){ odp[i][velkaci[i][j]] = kolo1; bol[i][kolo1] = 1; kolo1++; if(kolo1 == k) kolo1 -= k; } } vec<int> pos(n, 0); vec<int> poc(k, (n*m)/2); For(i, (n*m)/2){ sum -= p[i].ff; int ja = p[i].ss.ff; int ja_listok = p[i].ss.ss; while(bol[ja][pos[ja]] || poc[pos[ja]] == 0) pos[ja]++; odp[ja][ja_listok] = pos[ja]; poc[pos[ja]]--; pos[ja]++; } allocate_tickets(odp); return sum; }