#include "tickets.h" #include <vector> #include <algorithm> #include <iostream> #include <queue> #define ll long long #define For(i, n) for(int i = 0; i < n; i++) #define NEK 1000000000 #define vec vector #define pii pair<ll, ll> #define ff first #define ss second using namespace std; ll vyrob_vysledok_z_pola(vec<pair<int, pii>>&p, int n, int m, int k){ 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)); int polka = (n*k)/2; For(i, polka){ sum += p[i+polka].ff; int ja = p[i+polka].ss.ff; int ja_listok = p[i+polka].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, polka); For(i, polka){ 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; } long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); int poc1 = 0; vec<int> p1(n, 0), p2(n, m-k); priority_queue<pii> q; For(i, n){ q.push({(-1) * (x[i][p2[i]] + x[i][p1[i]]), i}); } int polka = (n*k)/2; For(i, polka){ ll w = q.top().ss; q.pop(); p1[w]++; p2[w]++; if(p2[w] >= x[w].size()) continue; q.push({(-1) * (x[w][p2[w]] + x[w][p1[w]]), w}); } vec<pair<int, pii>> p; For(i, n){ for(int j = 0; j < p1[i]; j++){ p.push_back({x[i][j], {i, j}}); } for(int j = p2[i]; j < m; j++){ p.push_back({x[i][j], {i, j}}); } } return vyrob_vysledok_z_pola(p, n, m, k); }