Submission #827012

#	Time	Username	Problem	Language	Result	Execution time	Memory
827012		erray	카니발 티켓 (IOI20_tickets)	C++17	27 / 100	395 ms	73064 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/day2/debug.h"
#else 
  #define debug(...) void(37)
#endif

long long find_maximum(int K, std::vector<std::vector<int>> X) {
  int N = int(X.size());
  int M = int(X[0].size());
  long long ans = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) {
      ans += X[i][M - 1 - j];
    }
  }
  priority_queue<pair<int, int>> pq;
  vector<int> pt(N);
  for (int i = 0; i < N; ++i) {
    pq.emplace(-X[i][0] - X[i][M - K], i);
  }
  int half = N * K / 2;
  while (half--) {
    auto[add, i] = pq.top();
    pq.pop();
    ans += add;
    if (++pt[i] < K) {
      pq.emplace(-X[i][pt[i]] - X[i][M - K + pt[i]], i);
    }
  }
  vector<int> big_pt(N);
  for (int i = 0; i < N; ++i) {
    big_pt[i] = K - pt[i];
  }
  vector<vector<int>> s(N, vector<int>(M, -1));
  for (int t = 0; t < K; ++t) {
    int left = N / 2;
    for (int i = 0; i < N; ++i) {
      if (pt[i] > 0 && left--) {
        --pt[i];
        s[i][pt[i]] = t;
      } else {
        s[i][M - big_pt[i]] = t;
        --big_pt[i];
      }
    }
  }
  allocate_tickets(s);
  debug(ans);
	return ans;
}

• 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