| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 336978 | zlxFTH | 카니발 티켓 (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tickets.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define Dval(c, i) d[c][O[c][i]]
using namespace std;
typedef long long LL;
typedef vector<int> Vec;
typedef pair<LL, LL> Pii;
LL find_maximum(LL k, vector<Vec> d) {
LL n = d.size(), m = d[0].size();
vector<Vec> O(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) O[i].push_back(j);
sort(O[i].begin(), O[i].end(), [&](LL a, LL b) { return d[i][a] < d[i][b]; });
}
LL prize = 0;
Vec plus(n, 0), minus(n, 0), take(n, 0);
priority_queue<Pii> Q;
for (int c = 0; c < n; ++c) {
for (int j = 0; j < k; ++j) prize -= Dval(c, j);
Q.push(make_pair(Dval(c, k - 1) + Dval(c, m - 1), c));
}
for (int i = 0; i < n * k / 2; ++i) {
Pii it = Q.top(); Q.pop();
prize += it.first;
int c = it.second, &pc = plus[c];
if (++pc < k) Q.push(make_pair(Dval(c, k - 1 - pc) + Dval(c, m - 1 - pc), c));
}
while (!Q.empty()) Q.pop();
for (int c = 0; c < n; ++c) Q.push(make_pair(plus[c], c));
vector<Vec> S(n, Vec(m, -1));
for (int ki = 0; ki < k; ++ki) {
for (int i = 0; i < n / 2; ++i) take[Q.top().second] = 1, Q.pop();
for (int c = 0; c < n; ++c) {
int &p = plus[c];
Vec &s = S[c];
if (take[c]) s[O[c][m - p]] = ki, Q.push(make_pair(--p, c)), take[c] = 0;
else s[minus[c]++] = ki;
}
}
allocate_tickets(S);
return prize;
}