| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1196363 | Gabp | Carnival Tickets (IOI20_tickets) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include"tickets.h"
using namespace std;
long long int find_maximum(int k, vector<vector<int>> x) {
int n = x.size(), m = x[0].size();
long long int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
total += x[i][m - j - 1];
}
}
vector<int> idx(n, 0);
priority_queue<pair<long long int,int>> pq;
for (int i = 0; i < n; i++) pq.push({-x[i][0] - x[i][m - k - 1], i});
int cnt = n * k / 2;
while (cnt--) {
auto [val, id] = pq.top(); pq.pop();
total += val;
idx[id]++;
if (idx[id] < k) {
pq.push({-x[i][idx[id]] - x[i][m - k - 1 + idx[id]], i});
}
}
vector<int> lo = idx;
vector<int> hi(n);
for (int i = 0; i < n; i++) hi[i] = k - lo[i];
vector<vector<int>> ans(n, vector<int>(m, -1));
for (int i = 0; i < k; i++) {
int l = n / 2, r = n / 2;
for (int j = 0; j < n; j++) {
if (lo[j] == 0) {
ans[j][m - hi[j]] = i;
hi[j]--;
r--;
} else if (hi[j] == 0) {
lo[j]--;
ans[j][lo[j]] = i;
l--;
}
}
for (int j = 0; j < n; j++) {
if (lo[j] + hi[j] != k - i) continue;
if (l) {
lo[j]--;
ans[j][lo[j]] = i;
l--;
} else {
ans[j][m - hi[j]] = i;
hi[j]--;
r--;
}
}
}
allocate_tickets(ans);
return total;
}