#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/day2/debug.h"
#else
#define debug(...) void(37)
#endif
long long find_maximum(int K, std::vector<std::vector<int>> X) {
int N = int(X.size());
int M = int(X[0].size());
long long ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < K; ++j) {
ans += X[i][M - 1 - j];
}
}
priority_queue<pair<int, int>> pq;
vector<int> pt(N);
for (int i = 0; i < N; ++i) {
pq.emplace(-X[i][0] - X[i][M - K], i);
}
int half = N * K / 2;
while (half--) {
auto[add, i] = pq.top();
pq.pop();
ans += add;
++pt[i];
if (pt[i] < K) {
pq.emplace(-X[i][pt[i]] - X[i][M - K + pt[i]], i);
}
}
assert(accumulate(pt.begin(), pt.end(), 0) == N * K / 2);
vector<int> big_pt(N);
for (int i = 0; i < N; ++i) {
big_pt[i] = K - pt[i];
}
vector<vector<int>> s(N, vector<int>(M, -1));
for (int t = 0; t < K; ++t) {
vector<int> bigs, smalls;
vector<bool> used(N);
for (int i = 0; i < N; ++i) {
used[i] = true;
if (pt[i] == K - t) {
--pt[i];
s[i][pt[i]] = t;
smalls.push_back(X[i][pt[i]]);
} else if (big_pt[i] == K - t) {
s[i][M - big_pt[i]] = t;
bigs.push_back(X[i][M - big_pt[i]]);
--big_pt[i];
} else {
used[i] = false;
}
}
for (int i = 0; i < N; ++i) {
if (used[i]) continue;
if (pt[i] > 0 && int(smalls.size()) < N / 2) {
--pt[i];
s[i][pt[i]] = t;
smalls.push_back(X[i][pt[i]]);
} else {
s[i][M - big_pt[i]] = t;
bigs.push_back(X[i][M - big_pt[i]]);
--big_pt[i];
}
}
assert(int(smalls.size()) <= N / 2);
assert(*max_element(smalls.begin(), smalls.end()) <= *min_element(bigs.begin(), bigs.end()));
}
allocate_tickets(s);
debug(ans);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
16 ms |
2388 KB |
Output is correct |
6 |
Correct |
400 ms |
51452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
15 ms |
2532 KB |
Output is correct |
6 |
Correct |
386 ms |
56760 KB |
Output is correct |
7 |
Correct |
398 ms |
57072 KB |
Output is correct |
8 |
Correct |
2 ms |
440 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
4 ms |
852 KB |
Output is correct |
13 |
Correct |
20 ms |
2132 KB |
Output is correct |
14 |
Correct |
18 ms |
2096 KB |
Output is correct |
15 |
Correct |
416 ms |
57684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
24 ms |
3208 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
532 ms |
75924 KB |
Output is correct |
9 |
Correct |
499 ms |
70932 KB |
Output is correct |
10 |
Correct |
494 ms |
71068 KB |
Output is correct |
11 |
Correct |
579 ms |
76008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
444 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
444 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
17 ms |
3156 KB |
Output is correct |
14 |
Correct |
17 ms |
3256 KB |
Output is correct |
15 |
Correct |
18 ms |
3276 KB |
Output is correct |
16 |
Correct |
20 ms |
3288 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
308 KB |
Output is correct |
20 |
Correct |
19 ms |
2608 KB |
Output is correct |
21 |
Correct |
18 ms |
3068 KB |
Output is correct |
22 |
Correct |
18 ms |
2644 KB |
Output is correct |
23 |
Correct |
20 ms |
3152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
16 ms |
2388 KB |
Output is correct |
12 |
Correct |
400 ms |
51452 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
15 ms |
2532 KB |
Output is correct |
18 |
Correct |
386 ms |
56760 KB |
Output is correct |
19 |
Correct |
398 ms |
57072 KB |
Output is correct |
20 |
Correct |
2 ms |
440 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
4 ms |
852 KB |
Output is correct |
25 |
Correct |
20 ms |
2132 KB |
Output is correct |
26 |
Correct |
18 ms |
2096 KB |
Output is correct |
27 |
Correct |
416 ms |
57684 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
24 ms |
3208 KB |
Output is correct |
33 |
Correct |
4 ms |
724 KB |
Output is correct |
34 |
Correct |
4 ms |
980 KB |
Output is correct |
35 |
Correct |
532 ms |
75924 KB |
Output is correct |
36 |
Correct |
499 ms |
70932 KB |
Output is correct |
37 |
Correct |
494 ms |
71068 KB |
Output is correct |
38 |
Correct |
579 ms |
76008 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
2 ms |
340 KB |
Output is correct |
42 |
Correct |
2 ms |
468 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
2 ms |
468 KB |
Output is correct |
45 |
Correct |
1 ms |
212 KB |
Output is correct |
46 |
Correct |
1 ms |
304 KB |
Output is correct |
47 |
Correct |
2 ms |
468 KB |
Output is correct |
48 |
Correct |
2 ms |
444 KB |
Output is correct |
49 |
Correct |
2 ms |
468 KB |
Output is correct |
50 |
Correct |
2 ms |
468 KB |
Output is correct |
51 |
Correct |
17 ms |
3156 KB |
Output is correct |
52 |
Correct |
17 ms |
3256 KB |
Output is correct |
53 |
Correct |
18 ms |
3276 KB |
Output is correct |
54 |
Correct |
20 ms |
3288 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
2 ms |
468 KB |
Output is correct |
57 |
Correct |
2 ms |
308 KB |
Output is correct |
58 |
Correct |
19 ms |
2608 KB |
Output is correct |
59 |
Correct |
18 ms |
3068 KB |
Output is correct |
60 |
Correct |
18 ms |
2644 KB |
Output is correct |
61 |
Correct |
20 ms |
3152 KB |
Output is correct |
62 |
Correct |
47 ms |
8388 KB |
Output is correct |
63 |
Correct |
46 ms |
8336 KB |
Output is correct |
64 |
Correct |
56 ms |
8520 KB |
Output is correct |
65 |
Correct |
203 ms |
33104 KB |
Output is correct |
66 |
Correct |
227 ms |
33628 KB |
Output is correct |
67 |
Correct |
4 ms |
980 KB |
Output is correct |
68 |
Correct |
4 ms |
800 KB |
Output is correct |
69 |
Correct |
415 ms |
73056 KB |
Output is correct |
70 |
Correct |
468 ms |
74012 KB |
Output is correct |
71 |
Correct |
546 ms |
75896 KB |
Output is correct |
72 |
Correct |
455 ms |
60516 KB |
Output is correct |
73 |
Correct |
516 ms |
73220 KB |
Output is correct |
74 |
Correct |
425 ms |
59040 KB |
Output is correct |
75 |
Correct |
466 ms |
71776 KB |
Output is correct |