#include <bits/stdc++.h>
#include "tickets.h"
using ll = long long;
using namespace std;
mt19937_64 mt(time(nullptr));
ll find_maximum(int k, vector<vector<int>> t) {
int n = t.size(), m = t[0].size(), oldm = m;
multiset<pair<int, int>> st;
vector<vector<int>> cost(n, vector<int>(k + 1, -1));
vector<int> ptr(n, 0);
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
res -= t[i][j];
cost[i][j] = t[i][m - 1 - j] + t[i][k - 1 - j];
}
}
for (int i = 0; i < n; i++) {
st.emplace(-cost[i][0], i);
}
for (int _ = 0; _ < n * k / 2; _++) {
auto [w, i] = *st.begin();
st.erase(st.begin());
res -= w;
st.emplace(-cost[i][++ptr[i]], i);
}
vector<vector<int>> nt(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k - ptr[i]; j++) {
nt[i].push_back(t[i][j]);
}
for (int j = ptr[i] - 1; j >= 0; j--) {
nt[i].push_back(t[i][m - 1 - j]);
}
}
t = nt;
m = k;
vector<int> all;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
all.push_back(t[i][j]);
}
}
sort(all.begin(), all.end());
int middle = all[all.size() / 2];
vector<pair<ll, int>> a(n);
vector<int> bg(n, 0), end(n, m - 1);
vector<vector<int>> s(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
a[i].first = 0;
a[i].second = i;
for (int j = 0; j < m; j++) {
t[i][j] -= middle;
}
}
int bgs = 0, ends = 0;
for (int i = 0; i < n; i++) {
for (int st = 0; st < k; st++) {
if ((abs(t[i][bg[i]]) > abs(t[i][end[i]]) && t[i][bg[i]] <= 0) || t[i][end[i]] < 0) {
bgs++;
bg[i]++;
} else {
ends++;
end[i]--;
}
}
}
if (bgs > ends) {
multiset<pair<int, int>> st;
for (int i = 0; i < n; i++) {
for (int j = bg[i] - 1; j >= 0; j--) {
int sw = end[i] - (bg[i] - j - 1);
if (t[i][sw] >= 0) {
st.emplace(-t[i][j] - t[i][sw], i);
}
}
}
while (bgs > ends) {
assert(!st.empty());
bgs--;
ends++;
auto [w, i] = *st.begin();
st.erase(st.begin());
bg[i]--;
end[i]--;
}
} else if (ends > bgs) {
multiset<pair<int, int>> st;
for (int i = 0; i < n; i++) {
for (int j = end[i] + 1; j < m; j++) {
int sw = bg[i] + j - end[i] - 1;
if (t[i][sw] <= 0) {
st.emplace(t[i][j] + t[i][sw], i);
}
}
}
while (bgs < ends) {
bgs++;
ends--;
auto [w, i] = *st.begin();
st.erase(st.begin());
bg[i]++;
end[i]++;
}
}
vector<int> l(n), r(n);
for (int i = 0; i < n; i++) {
l[i] = bg[i];
r[i] = m - end[i] - 1;
}
for (int st = 0; st < k; st++) {
vector<int> used(n, 0);
int bal = 0;
for (int i = 0; i < n; i++) {
if (l[i] == k - st) {
used[i] = 1;
l[i]--;
s[i][l[i]] = st;
bal--;
}
if (r[i] == k - st) {
used[i] = 1;
s[i][m - r[i]] = st;
r[i]--;
bal++;
}
}
for (int i = 0; i < n; i++) {
if (!used[i]) {
if (bal > 0) {
used[i] = 1;
l[i]--;
s[i][l[i]] = st;
bal--;
} else {
used[i] = 1;
s[i][m - r[i]] = st;
r[i]--;
bal++;
}
}
}
}
vector<vector<int>> ns(n, vector<int>(oldm, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k - ptr[i]; j++) {
ns[i][j] = s[i][j];
}
for (int j = ptr[i] - 1; j >= 0; j--) {
ns[i][oldm - 1 - j] = s[i][m - 1 - j];
}
}
allocate_tickets(ns);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
1112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
16 ms |
3420 KB |
Output is correct |
6 |
Correct |
389 ms |
73600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
20 ms |
3280 KB |
Output is correct |
6 |
Correct |
385 ms |
71916 KB |
Output is correct |
7 |
Correct |
412 ms |
75184 KB |
Output is correct |
8 |
Correct |
3 ms |
856 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
6 ms |
1372 KB |
Output is correct |
13 |
Correct |
20 ms |
3548 KB |
Output is correct |
14 |
Correct |
20 ms |
4080 KB |
Output is correct |
15 |
Correct |
655 ms |
112056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
27 ms |
4720 KB |
Output is correct |
6 |
Correct |
5 ms |
1112 KB |
Output is correct |
7 |
Correct |
6 ms |
1628 KB |
Output is correct |
8 |
Correct |
708 ms |
105976 KB |
Output is correct |
9 |
Correct |
652 ms |
101384 KB |
Output is correct |
10 |
Correct |
653 ms |
99112 KB |
Output is correct |
11 |
Correct |
700 ms |
107172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
2 ms |
856 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
516 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
600 KB |
Output is correct |
2 |
Correct |
2 ms |
856 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
516 KB |
Output is correct |
5 |
Correct |
2 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
17 ms |
3676 KB |
Output is correct |
14 |
Correct |
16 ms |
3408 KB |
Output is correct |
15 |
Correct |
21 ms |
4136 KB |
Output is correct |
16 |
Correct |
27 ms |
4808 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
2 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
24 ms |
3408 KB |
Output is correct |
21 |
Correct |
22 ms |
4092 KB |
Output is correct |
22 |
Correct |
22 ms |
4060 KB |
Output is correct |
23 |
Correct |
25 ms |
4560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
1112 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
440 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
16 ms |
3420 KB |
Output is correct |
12 |
Correct |
389 ms |
73600 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
20 ms |
3280 KB |
Output is correct |
18 |
Correct |
385 ms |
71916 KB |
Output is correct |
19 |
Correct |
412 ms |
75184 KB |
Output is correct |
20 |
Correct |
3 ms |
856 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
6 ms |
1372 KB |
Output is correct |
25 |
Correct |
20 ms |
3548 KB |
Output is correct |
26 |
Correct |
20 ms |
4080 KB |
Output is correct |
27 |
Correct |
655 ms |
112056 KB |
Output is correct |
28 |
Correct |
0 ms |
344 KB |
Output is correct |
29 |
Correct |
0 ms |
344 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
2 ms |
604 KB |
Output is correct |
32 |
Correct |
27 ms |
4720 KB |
Output is correct |
33 |
Correct |
5 ms |
1112 KB |
Output is correct |
34 |
Correct |
6 ms |
1628 KB |
Output is correct |
35 |
Correct |
708 ms |
105976 KB |
Output is correct |
36 |
Correct |
652 ms |
101384 KB |
Output is correct |
37 |
Correct |
653 ms |
99112 KB |
Output is correct |
38 |
Correct |
700 ms |
107172 KB |
Output is correct |
39 |
Correct |
1 ms |
600 KB |
Output is correct |
40 |
Correct |
2 ms |
856 KB |
Output is correct |
41 |
Correct |
2 ms |
604 KB |
Output is correct |
42 |
Correct |
2 ms |
516 KB |
Output is correct |
43 |
Correct |
2 ms |
604 KB |
Output is correct |
44 |
Correct |
2 ms |
604 KB |
Output is correct |
45 |
Correct |
1 ms |
344 KB |
Output is correct |
46 |
Correct |
1 ms |
600 KB |
Output is correct |
47 |
Correct |
2 ms |
604 KB |
Output is correct |
48 |
Correct |
2 ms |
604 KB |
Output is correct |
49 |
Correct |
2 ms |
604 KB |
Output is correct |
50 |
Correct |
2 ms |
604 KB |
Output is correct |
51 |
Correct |
17 ms |
3676 KB |
Output is correct |
52 |
Correct |
16 ms |
3408 KB |
Output is correct |
53 |
Correct |
21 ms |
4136 KB |
Output is correct |
54 |
Correct |
27 ms |
4808 KB |
Output is correct |
55 |
Correct |
1 ms |
348 KB |
Output is correct |
56 |
Correct |
2 ms |
604 KB |
Output is correct |
57 |
Correct |
2 ms |
604 KB |
Output is correct |
58 |
Correct |
24 ms |
3408 KB |
Output is correct |
59 |
Correct |
22 ms |
4092 KB |
Output is correct |
60 |
Correct |
22 ms |
4060 KB |
Output is correct |
61 |
Correct |
25 ms |
4560 KB |
Output is correct |
62 |
Correct |
47 ms |
8528 KB |
Output is correct |
63 |
Correct |
43 ms |
8540 KB |
Output is correct |
64 |
Correct |
74 ms |
11768 KB |
Output is correct |
65 |
Correct |
233 ms |
39272 KB |
Output is correct |
66 |
Correct |
307 ms |
45760 KB |
Output is correct |
67 |
Correct |
6 ms |
1624 KB |
Output is correct |
68 |
Correct |
4 ms |
1116 KB |
Output is correct |
69 |
Correct |
413 ms |
73924 KB |
Output is correct |
70 |
Correct |
535 ms |
89384 KB |
Output is correct |
71 |
Correct |
710 ms |
107064 KB |
Output is correct |
72 |
Correct |
491 ms |
89520 KB |
Output is correct |
73 |
Correct |
663 ms |
101336 KB |
Output is correct |
74 |
Correct |
419 ms |
74860 KB |
Output is correct |
75 |
Correct |
530 ms |
87164 KB |
Output is correct |