| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 336876 | chenwz | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
short id, color;
Node(LL v = 0, short i = 0, short 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 k = 0; k < K; ++k) {
sort(pos.begin(), pos.end(), [&](int a, int b) {
return cntL[a] > cntL[b];
}); // 每一轮从有限从cntL大的颜色来取, 所有的cntL加一起是nk/2
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]; // 前n/2个用的是L
else g[p][M - (++cr)] = k, ans += a[p][M - cr]; // 后面用的是R
}
}
allocate_tickets(g);
return ans;
}