Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "tickets.h"
- #include <vector>
- #include <algorithm>
- #include <iostream>
- using namespace std;
- const long long INF = 1e18;
- long long find_maximum(int k, vector<vector<int>> x) {
- int n = x.size();
- int m = x[0].size();
- vector<vector<int>> answer(n, vector<int>(m, -1));
- long long prize = 0;
- int MAX = 0;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- MAX = max(MAX, x[i][j]);
- }
- }
- if (k == 1) {
- vector<vector<long long>> dp(1+n, vector<long long>(1+n/2, -INF));
- dp[0][0] = 0;
- // dp on prefix and number of positives
- vector<vector<bool>> chosePositive(1+n, vector<bool>(1+n/2));
- // chosePositive allows backtracking
- for (int i = 0; i < n; ++i) {
- for (int pos = 0; 2*pos <= n; ++pos) {
- if (dp[i][pos] == -INF) continue;
- // do not choose positive
- long long v = dp[i][pos] - x[i].front();
- if (v > dp[i+1][pos]) {
- dp[i+1][pos] = v;
- chosePositive[i+1][pos] = false;
- }
- // choose positive (if possible)
- if (2*pos == n) continue; // no more positives
- v = dp[i][pos] + x[i].back();
- if (v > dp[i+1][pos+1]) {
- dp[i+1][pos+1] = v;
- chosePositive[i+1][pos+1] = true;
- }
- }
- }
- prize = dp[n][n>>1];
- // Now reconstruct answer
- for (int i = n, pos = n>>1; i >= 1; --i) {
- if (!chosePositive[i][pos]) answer[i-1][0] = 0;
- else answer[i-1][m-1] = 0, pos--;
- }
- } else if (m == k || MAX == 1) {
- vector<int> cnt[2], remain[2];
- cnt[0].resize(n), cnt[1].resize(n);
- remain[0].resize(n), remain[1].resize(n);
- vector<pair<int, int>> v;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) v.emplace_back(x[i][j], i);
- }
- sort(v.begin(), v.end());
- for (int i = 0; (i<<1) < n*m; ++i) {
- ++cnt[0][v[i].second];
- }
- for (int i = 0; i < n; ++i) {
- cnt[1][i] = m-cnt[0][i];
- remain[0][i] = cnt[0][i];
- remain[1][i] = cnt[1][i];
- }
- for (int i = 0; i < k; ++i) {
- int used0 = 0;
- for (int y = 0; y < n; ++y) {
- if (!remain[1][y]) { // zero
- prize -= x[y][cnt[0][y]-remain[0][y]];
- answer[y][cnt[0][y]-remain[0][y]] = i;
- --remain[0][y];
- ++used0;
- } else if (!remain[0][y]) { // one
- prize += x[y][cnt[0][y]+remain[1][y]-1];
- answer[y][cnt[0][y]+remain[1][y]-1] = i;
- --remain[1][y];
- }
- }
- for (int y = 0; y < n; ++y) { // both
- if (!remain[0][y] || !remain[1][y]) continue;
- if (2*used0 < n) {
- prize -= x[y][cnt[0][y]-remain[0][y]];
- answer[y][cnt[0][y]-remain[0][y]] = i;
- --remain[0][y];
- ++used0;
- } else {
- prize += x[y][cnt[0][y]+remain[1][y]-1];
- answer[y][cnt[0][y]+remain[1][y]-1] = i;
- --remain[1][y];
- }
- }
- }
- }
- allocate_tickets(answer);
- return prize;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement