Submission #827057

#	Time	Username	Problem	Language	Result	Execution time	Memory
827057		erray	카니발 티켓 (IOI20_tickets)	C++17	11 / 100	2 ms	724 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<pair<int, int>, int>> pq;
  vector<int> pt(N);
  for (int i = 0; i < N; ++i) {
    pq.emplace(pair{-X[i][0], -X[i][M - K]}, i);
  }
  int half = N * K / 2;
  while (half--) {
    auto[p, i] = pq.top();
    pq.pop();
    ans += p.first + p.second;
    if (++pt[i] < K) {
      int neg = X[i][pt[i]];
      int pos = X[i][M - K + pt[i]];
      pq.emplace(pair{-neg, -pos}, 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;
    vector<int> bigs, smalls;
    for (int i = 0; i < N; ++i) {
      if (pt[i] > 0 && left--) {
        --pt[i];
        s[i][pt[i]] = t;
        smalls.push_back(X[i][pt[i]]);
      } else {
        s[i][M - big_pt[i]] = t;
        bigs.push_back(X[i][M - big_pt[i]]);
        --big_pt[i];
      }
    }
    assert(*max_element(smalls.begin(), smalls.end()) <= *min_element(bigs.begin(), bigs.end()));
  }
  allocate_tickets(s);
  debug(ans);
	return ans;
}

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