#include "tickets.h"
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#define int long long
using namespace std;
long long find_maximum(signed k, vector<vector<signed>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<signed>> answer (n, vector<signed> (m, -1));
vector<int> alls;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
alls.push_back(x[i][j]);
}
}
nth_element(alls.begin(), alls.begin() + n/2 * m, alls.end());
int globalmedian = alls[n/2*m];
int ans = 0;
vector<pair<int, int>> tb (n, {0, m-1});
for (int i = 0; i < k; ++i) {
vector<int> bgains (n);
for (int j = 0; j < n; ++j) {
int top = x[j][tb[j].second] - globalmedian;
int bottom = globalmedian - x[j][tb[j].first];
bgains[j] = bottom - top;
}
vector<int> inds (n);
iota(inds.begin(), inds.end(), 0);
nth_element(inds.begin(), inds.begin() + n/2, inds.end(), [&](int a, int b){return bgains[a] > bgains[b];});
for (int bottom = 0; bottom < n/2; ++bottom) {
assert(x[inds[bottom]][tb[inds[bottom]].first] <= globalmedian);
ans += globalmedian - x[inds[bottom]][tb[inds[bottom]].first];
answer[inds[bottom]][tb[inds[bottom]].first] = i;
tb[inds[bottom]].first++;
}
for (int top = n/2; top < n; ++top) {
assert(x[inds[top]][tb[inds[top]].second] >= globalmedian);
ans += x[inds[top]][tb[inds[top]].second] - globalmedian;
answer[inds[top]][tb[inds[top]].second] = i;
tb[inds[top]].second--;
}
}
allocate_tickets(answer);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
284 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
280 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
284 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
17 ms |
3600 KB |
Output is correct |
6 |
Correct |
403 ms |
84084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
284 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
15 ms |
2972 KB |
Output is correct |
6 |
Correct |
382 ms |
66524 KB |
Output is correct |
7 |
Correct |
432 ms |
66548 KB |
Output is correct |
8 |
Correct |
2 ms |
552 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Incorrect |
1 ms |
212 KB |
Contestant returned 43 while correct return value is 45. |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
284 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
684 KB |
Output is correct |
7 |
Correct |
1 ms |
280 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
284 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
17 ms |
3600 KB |
Output is correct |
12 |
Correct |
403 ms |
84084 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
284 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
15 ms |
2972 KB |
Output is correct |
18 |
Correct |
382 ms |
66524 KB |
Output is correct |
19 |
Correct |
432 ms |
66548 KB |
Output is correct |
20 |
Correct |
2 ms |
552 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Incorrect |
1 ms |
212 KB |
Contestant returned 43 while correct return value is 45. |
23 |
Halted |
0 ms |
0 KB |
- |