Submission #835173

#	Time	Username	Problem	Language	Result	Execution time	Memory
835173		NeroZein	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	566 ms	102488 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std; 

const long long INF = 1e15;

long long find_maximum(int k, vector<vector<int>> x) {
  int n = x.size();
  int m = x[0].size();
  vector<vector<long long>> suf(n + 1, vector<long long> (m + 2)); 
  vector<vector<long long>> pref(n + 1, vector<long long> (m + 1)); 
  vector<int> tot;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      tot.push_back(x[i][j]); 
    }
  }
  sort(tot.begin(), tot.end()); 
  long long biggest_sum = accumulate(tot.begin(), tot.end(), 0LL);
  for (int i = 0; i < n * k / 2; ++i) {
    biggest_sum -= tot[i] * 2; 
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      pref[i][j] = pref[i][j - 1] + x[i - 1][j - 1];
    }
    for (int j = m; j >= 1; --j) {
      suf[i][j] = suf[i][j + 1] + x[i - 1][j - 1];
    }
    //biggest_sum += -pref[i][m / 2] + (pref[i][m] - pref[i][m / 2]);
  }
  int negs = n / 2 * k; 
  vector<vector<int>> path(n + 1, vector<int> (negs + 1)); 
  vector<vector<long long>> dp(n + 1, vector<long long> (negs + 1)); 
  fill(dp[0].begin(), dp[0].end(), -INF);
  dp[0][negs] = 0;
  for (int i = 1; i <= n; ++i) {
    fill(dp[i].begin(), dp[i].end(), -INF); 
    for (int j = negs; j >= 0; --j) {
      for (int l = 0; l <= min(k, negs - j); ++l) {
        long long c = dp[i - 1][j + l] - pref[i][l] + suf[i][m + 1 + l - k];
        if (c > dp[i][j]) {
          dp[i][j] = c;          
          path[i][j] = l; 
        }
      }
    }
  }
  vector<int> cnt_pos(k, k * n / 2); 
  vector<int> cnt_neg(k, k * n / 2); 
  vector<vector<int>> answer(n, vector<int> (m, -1));
  int row = n, col = 0;
  for (int i = 0; i < n; ++i) {
    int negatives = path[row][col];
    col = col + path[row][col];
    row--; 
    int z = 0; 
    vector<bool> used(k); 
    for (int j = 0; j < k && z < negatives; ++j) {
      if (cnt_neg[j]) {
        used[j] = true; 
        answer[row][z++] = j;
        cnt_neg[j]--; 
      }
    }
    assert(z == negatives); 
    z = 0;
    for (int j = 0; j < k && z < k - negatives; ++j) {
      if (!used[j] && cnt_pos[j]) {
        answer[row][m - z - 1] = j;
        cnt_pos[j]--;        
        z++; 
      }
    }
    assert(z == k - negatives); 
  }
  allocate_tickets(answer);
  //cout << "BIG: " << biggest_sum << endl; 
  if (m == k) {
    assert(dp[n][0] == biggest_sum); 
  }
  return dp[n][0];
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10