#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;
#define ST first
#define ND second
#define PB push_back
const int nax = 1500 + 10;
int take[nax];
void allocate_tickets(vector<vi> a);
ll find_maximum(int k, vector<vi>x) {
int n = (int)x.size();
int m = (int)x[0].size();
ll ans = 0;
for(int i = 0; i < k; ++i) {
for(int j = 0; j < n; ++j) {
ans -= x[j][i];
}
}
priority_queue<pi>PQ;
for(int i = 0; i < n; ++i) {
take[i] = 0;
PQ.push({x[i][m - 1] + x[i][k - 1], i});
}
int cur = 0;
while(cur < n * k / 2) {
cur++;
pi tp = PQ.top();
ans += tp.ST;
PQ.pop();
take[tp.ND]++;
if(take[tp.ND] < k) {
PQ.push({x[tp.ND][m - 1 - take[tp.ND]] + x[tp.ND][k - 1 - take[tp.ND]], tp.ND});
}
}
vector<vi>res(n);
for(int i = 0; i < n; ++i) res[i].resize(m, -1);
vector<vector<bool>>t(n);
for(int i = 0; i < n; ++i) t[i].resize(k+1);
for(int turn = k - 1; turn >= 0; --turn) {
cur = 0;
for(int i = 0; i < n; ++i) {
if(take[i] == turn + 1) {
t[i][turn] = 1;
cur++;
continue;
} else if(take[i] == 0) {
t[i][turn] = 0;
cur--;
continue;
}
}
for(int i = 0; i < n; ++i) {
if(take[i] == turn + 1 || take[i] == 0) continue;
if(cur < 0) {
t[i][turn] = 1;
cur++;
} else {
t[i][turn] = 0;
cur--;
}
}
for(int i = 0; i < n; ++i) {
if(t[i][turn]) take[i]--;
}
}
vi l(n, 0);
vi r(n, m-1);
for(int turn = 0; turn < k; ++turn) {
for(int i = 0; i < n; ++i) {
if(t[i][turn]) {
res[i][r[i]--] = turn;
} else {
res[i][l[i]++] = turn;
}
}
}
allocate_tickets(res);
//for(int i = 0; i < n; ++i) {
// for(int j = 0; j < m; ++j) {
// cout << res[i][j] << " ";
// }
// cout << "\n";
//}
return ans;
}
//int main() {
// cout << find_maximum(2, {{0, 2, 5},{1, 1, 3}}) << "\n";
// cout << find_maximum(1, {{5, 9}, {1, 4}, {3, 6}, {2, 7}}) << "\n";
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
268 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
29 ms |
3308 KB |
Output is correct |
6 |
Correct |
677 ms |
73484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
492 KB |
Output is correct |
5 |
Correct |
26 ms |
2668 KB |
Output is correct |
6 |
Correct |
644 ms |
57232 KB |
Output is correct |
7 |
Correct |
666 ms |
57452 KB |
Output is correct |
8 |
Correct |
4 ms |
620 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
7 ms |
876 KB |
Output is correct |
13 |
Correct |
22 ms |
2284 KB |
Output is correct |
14 |
Correct |
22 ms |
2284 KB |
Output is correct |
15 |
Correct |
707 ms |
58112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
36 ms |
3564 KB |
Output is correct |
6 |
Correct |
6 ms |
876 KB |
Output is correct |
7 |
Correct |
7 ms |
1132 KB |
Output is correct |
8 |
Correct |
886 ms |
76600 KB |
Output is correct |
9 |
Correct |
826 ms |
71380 KB |
Output is correct |
10 |
Correct |
817 ms |
71660 KB |
Output is correct |
11 |
Correct |
887 ms |
76612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
3 ms |
620 KB |
Output is correct |
6 |
Correct |
3 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
3 ms |
492 KB |
Output is correct |
10 |
Correct |
3 ms |
620 KB |
Output is correct |
11 |
Correct |
3 ms |
492 KB |
Output is correct |
12 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
3 ms |
620 KB |
Output is correct |
5 |
Correct |
3 ms |
620 KB |
Output is correct |
6 |
Correct |
3 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
3 ms |
492 KB |
Output is correct |
10 |
Correct |
3 ms |
620 KB |
Output is correct |
11 |
Correct |
3 ms |
492 KB |
Output is correct |
12 |
Correct |
3 ms |
620 KB |
Output is correct |
13 |
Correct |
29 ms |
3436 KB |
Output is correct |
14 |
Correct |
31 ms |
3336 KB |
Output is correct |
15 |
Correct |
31 ms |
3308 KB |
Output is correct |
16 |
Correct |
33 ms |
3436 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
3 ms |
620 KB |
Output is correct |
19 |
Correct |
2 ms |
492 KB |
Output is correct |
20 |
Correct |
28 ms |
2796 KB |
Output is correct |
21 |
Correct |
32 ms |
3308 KB |
Output is correct |
22 |
Correct |
29 ms |
2796 KB |
Output is correct |
23 |
Correct |
34 ms |
3436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
268 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
512 KB |
Output is correct |
6 |
Correct |
3 ms |
892 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
3 ms |
620 KB |
Output is correct |
11 |
Correct |
29 ms |
3308 KB |
Output is correct |
12 |
Correct |
677 ms |
73484 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
3 ms |
492 KB |
Output is correct |
17 |
Correct |
26 ms |
2668 KB |
Output is correct |
18 |
Correct |
644 ms |
57232 KB |
Output is correct |
19 |
Correct |
666 ms |
57452 KB |
Output is correct |
20 |
Correct |
4 ms |
620 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
384 KB |
Output is correct |
24 |
Correct |
7 ms |
876 KB |
Output is correct |
25 |
Correct |
22 ms |
2284 KB |
Output is correct |
26 |
Correct |
22 ms |
2284 KB |
Output is correct |
27 |
Correct |
707 ms |
58112 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
3 ms |
620 KB |
Output is correct |
32 |
Correct |
36 ms |
3564 KB |
Output is correct |
33 |
Correct |
6 ms |
876 KB |
Output is correct |
34 |
Correct |
7 ms |
1132 KB |
Output is correct |
35 |
Correct |
886 ms |
76600 KB |
Output is correct |
36 |
Correct |
826 ms |
71380 KB |
Output is correct |
37 |
Correct |
817 ms |
71660 KB |
Output is correct |
38 |
Correct |
887 ms |
76612 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
3 ms |
620 KB |
Output is correct |
41 |
Correct |
3 ms |
620 KB |
Output is correct |
42 |
Correct |
3 ms |
620 KB |
Output is correct |
43 |
Correct |
3 ms |
620 KB |
Output is correct |
44 |
Correct |
3 ms |
620 KB |
Output is correct |
45 |
Correct |
1 ms |
364 KB |
Output is correct |
46 |
Correct |
1 ms |
364 KB |
Output is correct |
47 |
Correct |
3 ms |
492 KB |
Output is correct |
48 |
Correct |
3 ms |
620 KB |
Output is correct |
49 |
Correct |
3 ms |
492 KB |
Output is correct |
50 |
Correct |
3 ms |
620 KB |
Output is correct |
51 |
Correct |
29 ms |
3436 KB |
Output is correct |
52 |
Correct |
31 ms |
3336 KB |
Output is correct |
53 |
Correct |
31 ms |
3308 KB |
Output is correct |
54 |
Correct |
33 ms |
3436 KB |
Output is correct |
55 |
Correct |
1 ms |
364 KB |
Output is correct |
56 |
Correct |
3 ms |
620 KB |
Output is correct |
57 |
Correct |
2 ms |
492 KB |
Output is correct |
58 |
Correct |
28 ms |
2796 KB |
Output is correct |
59 |
Correct |
32 ms |
3308 KB |
Output is correct |
60 |
Correct |
29 ms |
2796 KB |
Output is correct |
61 |
Correct |
34 ms |
3436 KB |
Output is correct |
62 |
Correct |
75 ms |
8556 KB |
Output is correct |
63 |
Correct |
76 ms |
8556 KB |
Output is correct |
64 |
Correct |
93 ms |
8684 KB |
Output is correct |
65 |
Correct |
339 ms |
33388 KB |
Output is correct |
66 |
Correct |
376 ms |
33900 KB |
Output is correct |
67 |
Correct |
7 ms |
1132 KB |
Output is correct |
68 |
Correct |
6 ms |
876 KB |
Output is correct |
69 |
Correct |
675 ms |
73300 KB |
Output is correct |
70 |
Correct |
781 ms |
74476 KB |
Output is correct |
71 |
Correct |
881 ms |
76608 KB |
Output is correct |
72 |
Correct |
759 ms |
61036 KB |
Output is correct |
73 |
Correct |
872 ms |
73684 KB |
Output is correct |
74 |
Correct |
692 ms |
59468 KB |
Output is correct |
75 |
Correct |
788 ms |
72300 KB |
Output is correct |