#include <bits/stdc++.h>
using namespace std;
#include "tickets.h"
using ll = long long;
/*
static int n;
static int m;
static int k;
static std::vector<std::vector<int>> d;
static std::vector<std::vector<int>> x;
static int called = 0;
static void check(bool cond, std::string message) {
if (!cond) {
printf("%s\n", message.c_str());
exit(0);
}
}
void allocate_tickets( std::vector<std::vector<int>> _d) {
check(!called, "allocate_tickets called more than once");
d = _d;
check((int)d.size() == n, "allocate_tickets called with parameter of wrong size");
for (int i = 0; i < n; i++) {
check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size");
}
called = 1;
}
*/
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> to_alloc(n, vector<int>(m, -1));
ll tot = 0;
for(int i=0;i<n;++i) for(int j=0;j<k;++j) tot -= x[i][j];
vector<stack<ll>> toks(n);
vector<int> pluses(n, 0), plus_a(n, m-1), minus_a(n, 0);
for(int i=0;i<n;++i) for(int j=0;j<k;++j) {
toks[i].push(x[i][j]+x[i][m-k+j]);
}
priority_queue<pair<ll,int>> pq;
for(int i=0;i<n;++i) {
pq.push({toks[i].top(), i});
toks[i].pop();
}
for(int t=0;t<k*n/2;++t){
auto [val, i] = pq.top(); pq.pop();
pluses[i]++; tot += val;
if (!toks[i].empty()) {
pq.push({toks[i].top(), i});
toks[i].pop();
}
}
priority_queue<pair<int,int>> pq2;
for(int i=0;i<n;++i) pq2.push({pluses[i], i});
vector<int> chosen(n, 0);
for(int r=0;r<k;++r){
for(int i=0;i<n/2;++i){
auto [val, j] = pq2.top(); pq2.pop();
chosen[j] = 1;
}
for(int i=0;i<n;++i){
if (chosen[i]){
to_alloc[i][plus_a[i]--] = r;
pq2.push({--pluses[i], i});
}
else {
to_alloc[i][minus_a[i]++] = r;
}
chosen[i] = 0;
}
}
allocate_tickets(to_alloc);
return tot;
return tot;
return 0;
}
/*
int main() {
assert(scanf("%d %d %d", &n, &m, &k) == 3);
x.resize(n);
for (int i = 0; i < n; i++) {
x[i].resize(m);
for (int j=0; j < m; j++) {
assert(scanf("%d", &x[i][j]) == 1);
}
}
fclose(stdin);
long long answer = find_maximum(k, x);
check(called, "failure to call allocate_tickets");
printf("%lld\n", answer);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j) printf(" ");
printf("%d", d[i][j]);
}
printf("\n");
}
fclose(stdout);
return 0;
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |