제출 #336853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336853		chenwz	카니발 티켓 (IOI20_tickets)	C++14	100 / 100	862 ms	54636 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 ansL(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();
    int id = x.id + 1, c = x.color;
    if (id == K) ansL[c] = K;
    else Q.push(Node(a[c][id] + a[c][M - K + id], id, c));
  }
  while (!Q.empty()) ansL[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 ansL[a] > ansL[b];});
    for (int i = 0; i < N; ++i) {
      int p = pos[i];
      if (i < (N >> 1)) g[p][--ansL[p]] = k, ans -= a[p][ansL[p]];
      else g[p][M - (++cntR[p])] = k, ans += a[p][M - cntR[p]];
    }
  }
  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