/*
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
#ifndef DEBUG
#include "tickets.h"
#endif
#ifdef DEBUG
vvi ta;
void allocate_tickets(const vvi& a_ta) {
LI(i, 0, (int)ta.size()) {
copy(a_ta[i].begin(), a_ta[i].end(), back_inserter(ta[i]));
}
}
#endif
ll find_maximum(int k, vvi x) {
int n = x.size(), m = x[0].size();
vvi talloc;
LI(i, 0, n) {
vi tallocr(m, -1);
talloc.pb(tallocr);
}
ll ans = 0ll;
/*
It's time to full point this problem! >:D
So uhh
for each color, pick k tickets
it's always optimal to pick a prefix/suffix
Tapos, the total number of "max" tickets must equal kn / 2
Same for min tickets
same thing as subtask 1, let's start with like, all mins
Then, we pair each minimum with the maximum
tapos, the oppcost is just min + max again, since by removing a min we increase by that value,
tapos we increase by max ulit, so the net effect is just the sum of min + max
Hmm, wait, is it possible, given some initial picking of max and min, that we can assign the k rounds
so that it works??
hmm
+00000
+++000
+++++0
0-----
000---
00000-
+00000|0-----
++0000|10----
++++++|210122
0-----|-22211
00----|--1000
000000|------
Consider nk points. Now, consider the median line
Oh, we can do some kind of pqueue siguro, no? haha
or kailangan ba? hmm, kasi like, pwede naman i-sort ulit
in O(n log n)
Tapos, we have k rounds, so O(k n log n) siya
Finally, since k is O(m), the final complexity is O(mn log n),
which works naman. No need for pqueue, pampasakit lamang yun sa ulo para sa
implementation haha (baka sumabog pa ang utak ko lol)
also why am I suddenly writing Taglish LOL
ANYWAYS, that handles the assignment part of the problem
now, we need to quickly construct the subset, haha
paano yun though?
so, for every color, there is a corresponding opportunity cost
(wow, just like in economics, where every decision has a corresponding opportunity cost)
o, tapos, i-max-pqueue nalang natin yung <min + max> per color, then repeat the process kn/2 times
finally, kung may kulay na wala nang min tickets, assign it a cost of like -infinity or just remove it from the pqueue
actually, wait, kailangan nga ba ng pqueue? idts
*/
// Augment x with indices
vvpi xwind;
xwind.reserve(n);
LI(i, 0, n) {
vpi xwindr;
xwindr.reserve(m);
LI(j, 0, m) {
xwindr.pb({x[i][j], j});
}
sort(xwindr.begin(), xwindr.end());
xwind.pb(xwindr);
}
// Representation: pair<opcost :: ll, inds :: pi>, tapos sort it decreasing
typedef pair<ll, pi> opcost;
vector<opcost> opcosts; // Thanks again MA'AM BAMBIE
LI(i, 0, n) {
LI(j, 0, k) {
int t1 = xwind[i][j].fi, t2 = xwind[i][j - k + m].fi;
opcosts.pb({t1 + t2, {i, j}});
}
}
sort(opcosts.begin(), opcosts.end(), greater<opcost>()); // It's time to be greedy
typedef vector<deque<int>> picked_t;
picked_t picked; // ! normal_i_ind -> xwind_j_ind (need to convert sorted ind "xwind_j_ind" to normal ind, this should be accessible from xwind naman)
vpi num_max;
LI(i, 0, n) {
deque<int> picked_r;
picked.pb(picked_r);
num_max.pb({0, i});
}
LI(i, 0, k * n) {
// Mark these to be done greedily
auto [_, ind_pair] = opcosts[i]; // Man, I wished we had auto [_, [i1, i2]] for structured bindings, like in JavaScript :(
auto [i1, i2] = ind_pair;
bool is_max = i < ((k * n) >> 1);
int picked_ind = is_max ? i2 - k + m : i2; // ! lots of math, check this again!
picked[i1].push_front(picked_ind);
if(is_max) num_max[i1].fi++;
ans = ans + (is_max ? (ll)xwind[i1][picked_ind].fi : -(ll)xwind[i1][picked_ind].fi);
}
// Eyoo, it passes sample test case??
// Allocation time
LI(i, 0, k) {
// Sort the colors by number of maxes to assign
sort(num_max.begin(), num_max.end(), greater<pi>());
LI(j, 0, n >> 1) {
// assign maxes
int i1 = num_max[j].se;
int i2 = picked[i1].back();
int xspace_i2 = xwind[i1][i2].se;
talloc[i1][xspace_i2] = i;
picked[i1].pop_back();
num_max[j].fi--;
}
LI(j, n >> 1, n) {
// assign mins
int i1 = num_max[j].se;
int i2 = picked[i1].front();
int xspace_i2 = xwind[i1][i2].se;
talloc[i1][xspace_i2] = i;
picked[i1].pop_front();
}
}
allocate_tickets(talloc);
return ans;
}
#ifdef DEBUG
int main() {
int n, m, k;
cin >> n >> m >> k;
vvi x;
LI(i, 0, n) {
vi xr(m, 0);
vi tar;
INPV(xr);
x.pb(xr);
ta.pb(tar);
}
cout << find_maximum(k, x) << "\n";
LI(i, 0, n) {
LI(j, 0, m) cout << ta[i][j] << " ";
cout << "\n";
}
return 0;
}
#endif
