제출 #827106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827106		erray	카니발 티켓 (IOI20_tickets)	C++17	100 / 100	579 ms	76008 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;
    ++pt[i];
    if (pt[i] < K) {
      pq.emplace(-X[i][pt[i]] - X[i][M - K + pt[i]], i);
    }
  }
  assert(accumulate(pt.begin(), pt.end(), 0) == N * K / 2);
  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) {
    vector<int> bigs, smalls;
    vector<bool> used(N);
    for (int i = 0; i < N; ++i) {
      used[i] = true;
      if (pt[i] == K - t) {
        --pt[i];
        s[i][pt[i]] = t;
        smalls.push_back(X[i][pt[i]]);
      } else if (big_pt[i] == K - t) {
        s[i][M - big_pt[i]] = t;
        bigs.push_back(X[i][M - big_pt[i]]);
        --big_pt[i];
      } else {
        used[i] = false;
      }
    }
    for (int i = 0; i < N; ++i) {
      if (used[i]) continue;
      if (pt[i] > 0 && int(smalls.size()) < N / 2) {
        --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(int(smalls.size()) <= N / 2);
    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: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10