#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define len(v) (int) (v.size())
#define all(v) v.begin(), v.end()
using ll = long long;
long long find_maximum(int k, vector<vector<int>> x) {
int n = len(x);
int m = len(x[0]);
vector answer(n, vector(m, -1));
vector<int> cnt(n, 0);
priority_queue<pair<int, int>> delta;
for (int i = 0; i < n; i++) {
delta.push({x[i][k - 1] + x[i][m - 1], i});
}
for (int z = 0; z < n * k / 2; z++) {
auto [_, i] = delta.top();
delta.pop();
cnt[i]++;
if (cnt[i] < k) {
delta.push({x[i][k - 1 - cnt[i]] + x[i][m - 1 - cnt[i]], i});
}
}
vector<int> idx(n);
iota(all(idx), 0ll);
vector<int> ptr_l(n, 0), ptr_r(n, m - 1);
ll score = 0;
for (int ki = 0; ki < k; ki++) {
sort(all(idx), [&] (int i, int j) {
return cnt[i] < cnt[j];
});
for (int i = 0; i < n / 2; i++) {
int j = idx[i];
score -= x[j][ptr_l[j]];
answer[j][ptr_l[j]++] = ki;
}
for (int i = n / 2; i < n; i++) {
int j = idx[i];
score += x[j][ptr_r[j]];
cnt[i]--;
answer[j][ptr_r[j]--] = ki;
}
}
allocate_tickets(answer);
return score;
}
# | 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... |