Submission #336863

#	Time	Username	Problem	Language	Result	Execution time	Memory
336863		chenwz	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	860 ms	54668 KiB

tickets

#include<algorithm>
#include<vector>
#include<queue>
#include "tickets.h"
using namespace std;
typedef long long LL;
const int NN = 1508;
typedef vector<int> VI;
struct Node {
  LL val;
  int id, color;
  Node(LL v = 0, int i = 0, int c = 0) : val(v), id(i), color(c) {}
  bool operator < (const Node& nd) const { return val > nd.val; }
};
LL find_maximum(int K, vector<VI> a) {
  priority_queue<Node> Q;
  int N = a.size(), M = a[0].size();
  VI cntL(N), cntR(N), pos(N);
  for (int c = 0; c < N; ++c) // 每种颜色，本身已经递增排序了
    Q.push(Node(a[c][0] + a[c][M - K], 0, c));
  int cnt = N * K / 2;
  for (int i = 1; i <= cnt; ++i) {
    Node x = Q.top(); Q.pop(); // 选择一个最小的(Li+Ri)来减
    int id = x.id + 1, c = x.color;
    if (id == K) cntL[c] = K;
    else Q.push(Node(a[c][id] + a[c][M - K + id], id, c));
  }
  while (!Q.empty()) cntL[Q.top().color] = Q.top().id, Q.pop();

  LL ans = 0;
  vector<VI> g(N, VI(M, -1));
  for (int i = 0; i < N; ++i) pos[i] = i;
  for (int k = 0; k < K; ++k) {
    sort(pos.begin(), pos.end(), [&](int a, int b) {
      return cntL[a] > cntL[b];
    });
    for (int c = 0; c < N; ++c) {
      int p = pos[c], &cl = cntL[p], &cr = cntR[p];
      if (2 * c < N) g[p][--cl] = k, ans -= a[p][cl];
      else g[p][M - (++cr)] = k, ans += a[p][M - cr];
    }
  }
  allocate_tickets(g);
  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