#include <iostream> #include <algorithm> #include <map> #include <vector> #include <queue> #include <set> #include "tickets.h" using namespace std; #define ll long long vector<vector<ll>> x; vector<vector<pair<ll, ll>>> dp; ll n, m; pair<ll, ll> makeDp(ll indx, ll used_high){ if(used_high > indx+1) return{-1, -1}; if(dp[indx][used_high].first != -1) return dp[indx][used_high]; if(indx == 0){ if(used_high == 1) return dp[indx][used_high] = {x[indx][m-1], m-1}; if(used_high == 0) return dp[indx][used_high] = {-x[indx][0], 0}; } dp[indx][used_high] = {makeDp(indx-1, used_high).first - (ll)x[indx][0], 0}; if(used_high && dp[indx][used_high].first < makeDp(indx-1, used_high-1).first + (ll)x[indx][m-1]){ dp[indx][used_high] = {makeDp(indx-1, used_high-1).first + (ll)x[indx][m-1], m-1}; } return dp[indx][used_high]; } ll find_maximum(int k, vector<vector<int>> x1){ n = x1.size(); m = x1[0].size(); x.assign(n, vector<ll>(m, 0)); vector<vector<int>> arr(n, vector<int>(m, -1)); ll ans = 0; for(int i = 0; i<n; i++) for(int j = 0; j<m; j++) x[i][j] = (ll)x1[i][j]; if(m == 1){ sort(x.begin(), x.end()); for(ll i = 0; i<n/2; i++) ans -= (ll)x[i][0]; for(ll i = n/2; i<n; i++) ans += (ll)x[i][0]; return ans; } else if(k == 1){ dp.assign(n, vector<pair<ll, ll>>(n, pair<ll, ll>(-1, -1))); ans = makeDp(n-1, n/2).first; ll uh = n/2; for(ll i = n-1; i>=0; i--){ arr[i][dp[i][uh].second] = 0; if(dp[i][uh].second == m-1) uh--; } return ans; } else if(k == m){ vector<int> allValues; for(int i = 0; i<n; i++) for(int j = 0; j<m; j++) allValues.push_back(x[i][j]); sort(allValues.begin(), allValues.end()); map<int, int> smallV; for(int i = 0; i<(n*m)/2; i++) smallV[allValues[i]] ++; for(int i = 0; i<n; i++) for(int j = 0; j<m; j++) { if(smallV[x[i][j]]){ smallV[x[i][j]]--; ans -= (ll)x[i][j]; x[i][j] = 0; } else{ ans += (ll)x[i][j]; x[i][j] = 1; } } priority_queue<pair<int, int>> pq; vector<int> takenZ(n, 0); for(int i = 0; i<n; i++){ pair<int, int> p = {0, i}; for(int j = 0; j<m; j++) p.first += x[i][j]; pq.push(p); } for(int i = 0; i<k; i++){ vector<pair<int, int>> add; int j = 0; while(j<n/2){ add.push_back(pq.top()); add[j].first --; arr[pq.top().second][m - pq.top().first] = i; j++; pq.pop(); } while(!pq.empty()){ arr[pq.top().second][takenZ[pq.top().second]] = i; takenZ[pq.top().second] ++; add.push_back(pq.top()); pq.pop(); } for(int i = 0; i<add.size(); i++) pq.push(add[i]); } // allocate_tickets(arr); } else{ priority_queue<pair<int, int>> pq; vector<int> takenZ(n, 0); for(int i = 0; i<n; i++){ pair<int, int> p = {0, i}; for(int j = 0; j<m; j++) p.first += x[i][j]; pq.push(p); } for(int i = 0; i<k; i++){ vector<pair<int, int>> add; int j = 0; while((j<n/2 || pq.top().first == m-i) && pq.top().first != 0){ add.push_back(pq.top()); add[j].first --; arr[pq.top().second][m - pq.top().first] = i; j++; pq.pop(); } while(!pq.empty()){ arr[pq.top().second][takenZ[pq.top().second]] = i; takenZ[pq.top().second] ++; add.push_back(pq.top()); pq.pop(); } for(int i = 0; i<add.size(); i++) pq.push(add[i]); ans += (ll)min((ll)j, (ll)n-j); } } allocate_tickets(arr); return ans; } // int main(void){ // freopen("input.txt", "r", stdin); // int n1, m1, k1; // cin>>n1>>m1>>k1; // vector<vector<int>> t; // t.assign(n1, vector<int>(m1, 0)); // for(int i = 0; i<n1; i++) for(int j = 0; j<m1; j++) cin>>t[i][j]; // cout<<find_maximum(k1, t); // }