#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
void allocate_tickets(std::vector <std::vector <int>> s);
int n, m;
ull find_maximum(int k, std::vector <std::vector <int>> x) {
n = x.size();
m = x[0].size();
ll r = 0;
for (int i = 0; i < n; i++)
for (int j = m - 1; j > m - 1 - k; j--)
r += x[i][j];
std::vector <std::pair <int, int>> range(n, { -1, m - k });
std::priority_queue <std::pair <int, int>> pq;
for (int i = 0; i < n; i++)
pq.push({ - x[i][range[i].first + 1] - x[i][range[i].second], i });
for (int i = 0; i < (n * k) >> 1; i++) {
auto p = pq.top(); pq.pop();
r += p.first;
range[p.second].first++, range[p.second].second++;
if (range[p.second].second == m) continue;
pq.push({ - x[p.second][range[p.second].first + 1] - x[p.second][range[p.second].second], p.second });
}
std::vector <std::vector <int>> mx(n), mn(n), mxi(n), mni(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= range[i].first; j++)
mn[i].push_back(x[i][j]), mni[i].push_back(j);
for (int j = range[i].second; j < m; j++)
mx[i].push_back(x[i][j]), mxi[i].push_back(j);;
std::reverse(mn[i].begin(), mn[i].end());
std::reverse(mni[i].begin(), mni[i].end());
}
std::vector <std::vector <int>> ans(n, std::vector <int> (m, -1));
for (int i = 0; i < k; i++) {
int hasmn = 0;
std::vector <int> mnmx(n, 0);
std::priority_queue <std::pair <int, int>> pqq;
for (int j = 0; j < n; j++) {
if (mx[j].size()) {
mnmx[j] = 1;
if (mn[j].size()) {
pqq.push({ - mn[j].back() - mx[j].back(), j });
}
} else {
mnmx[j] = -1;
hasmn++;
}
}
while (hasmn < (n >> 1)) {
auto p = pqq.top(); pqq.pop();
mnmx[p.second] = -1;
hasmn++;
}
for (int j = 0; j < n; j++) {
if (mnmx[j] == 1) {
ans[j][mxi[j].back()] = i;
mx[j].pop_back();
mxi[j].pop_back();
} else {
ans[j][mni[j].back()] = i;
mn[j].pop_back();
mni[j].pop_back();
}
}
}
allocate_tickets(ans);
return r;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
31 ms |
2432 KB |
Output is correct |
6 |
Correct |
730 ms |
51704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
27 ms |
3072 KB |
Output is correct |
6 |
Correct |
716 ms |
64808 KB |
Output is correct |
7 |
Correct |
842 ms |
69752 KB |
Output is correct |
8 |
Correct |
4 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
10 ms |
1024 KB |
Output is correct |
13 |
Correct |
25 ms |
2816 KB |
Output is correct |
14 |
Correct |
24 ms |
2792 KB |
Output is correct |
15 |
Correct |
868 ms |
72964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
6 ms |
512 KB |
Output is correct |
5 |
Correct |
64 ms |
3704 KB |
Output is correct |
6 |
Correct |
12 ms |
860 KB |
Output is correct |
7 |
Correct |
10 ms |
1312 KB |
Output is correct |
8 |
Correct |
1290 ms |
78644 KB |
Output is correct |
9 |
Correct |
1168 ms |
74888 KB |
Output is correct |
10 |
Correct |
1194 ms |
73392 KB |
Output is correct |
11 |
Correct |
1210 ms |
78520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
512 KB |
Output is correct |
3 |
Correct |
4 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
4 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
512 KB |
Output is correct |
3 |
Correct |
4 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
4 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
30 ms |
2448 KB |
Output is correct |
14 |
Correct |
41 ms |
2424 KB |
Output is correct |
15 |
Correct |
37 ms |
3064 KB |
Output is correct |
16 |
Correct |
46 ms |
3704 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
3 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
44 ms |
3064 KB |
Output is correct |
21 |
Correct |
36 ms |
2936 KB |
Output is correct |
22 |
Correct |
41 ms |
3448 KB |
Output is correct |
23 |
Correct |
45 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
1024 KB |
Output is correct |
7 |
Correct |
1 ms |
324 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
31 ms |
2432 KB |
Output is correct |
12 |
Correct |
730 ms |
51704 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
4 ms |
512 KB |
Output is correct |
17 |
Correct |
27 ms |
3072 KB |
Output is correct |
18 |
Correct |
716 ms |
64808 KB |
Output is correct |
19 |
Correct |
842 ms |
69752 KB |
Output is correct |
20 |
Correct |
4 ms |
640 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
0 ms |
256 KB |
Output is correct |
23 |
Correct |
1 ms |
256 KB |
Output is correct |
24 |
Correct |
10 ms |
1024 KB |
Output is correct |
25 |
Correct |
25 ms |
2816 KB |
Output is correct |
26 |
Correct |
24 ms |
2792 KB |
Output is correct |
27 |
Correct |
868 ms |
72964 KB |
Output is correct |
28 |
Correct |
0 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
6 ms |
512 KB |
Output is correct |
32 |
Correct |
64 ms |
3704 KB |
Output is correct |
33 |
Correct |
12 ms |
860 KB |
Output is correct |
34 |
Correct |
10 ms |
1312 KB |
Output is correct |
35 |
Correct |
1290 ms |
78644 KB |
Output is correct |
36 |
Correct |
1168 ms |
74888 KB |
Output is correct |
37 |
Correct |
1194 ms |
73392 KB |
Output is correct |
38 |
Correct |
1210 ms |
78520 KB |
Output is correct |
39 |
Correct |
1 ms |
256 KB |
Output is correct |
40 |
Correct |
4 ms |
512 KB |
Output is correct |
41 |
Correct |
4 ms |
512 KB |
Output is correct |
42 |
Correct |
3 ms |
512 KB |
Output is correct |
43 |
Correct |
4 ms |
512 KB |
Output is correct |
44 |
Correct |
3 ms |
512 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |
46 |
Correct |
1 ms |
384 KB |
Output is correct |
47 |
Correct |
3 ms |
512 KB |
Output is correct |
48 |
Correct |
3 ms |
512 KB |
Output is correct |
49 |
Correct |
3 ms |
512 KB |
Output is correct |
50 |
Correct |
3 ms |
512 KB |
Output is correct |
51 |
Correct |
30 ms |
2448 KB |
Output is correct |
52 |
Correct |
41 ms |
2424 KB |
Output is correct |
53 |
Correct |
37 ms |
3064 KB |
Output is correct |
54 |
Correct |
46 ms |
3704 KB |
Output is correct |
55 |
Correct |
1 ms |
384 KB |
Output is correct |
56 |
Correct |
3 ms |
512 KB |
Output is correct |
57 |
Correct |
2 ms |
512 KB |
Output is correct |
58 |
Correct |
44 ms |
3064 KB |
Output is correct |
59 |
Correct |
36 ms |
2936 KB |
Output is correct |
60 |
Correct |
41 ms |
3448 KB |
Output is correct |
61 |
Correct |
45 ms |
3320 KB |
Output is correct |
62 |
Correct |
81 ms |
6264 KB |
Output is correct |
63 |
Correct |
84 ms |
6136 KB |
Output is correct |
64 |
Correct |
135 ms |
8952 KB |
Output is correct |
65 |
Correct |
495 ms |
28764 KB |
Output is correct |
66 |
Correct |
598 ms |
33784 KB |
Output is correct |
67 |
Correct |
9 ms |
1280 KB |
Output is correct |
68 |
Correct |
7 ms |
768 KB |
Output is correct |
69 |
Correct |
741 ms |
51832 KB |
Output is correct |
70 |
Correct |
1136 ms |
64736 KB |
Output is correct |
71 |
Correct |
1391 ms |
78584 KB |
Output is correct |
72 |
Correct |
1076 ms |
76408 KB |
Output is correct |
73 |
Correct |
1211 ms |
75740 KB |
Output is correct |
74 |
Correct |
1058 ms |
63208 KB |
Output is correct |
75 |
Correct |
978 ms |
62968 KB |
Output is correct |