#include <bits/stdc++.h>
#include "tickets.h"
#define ll long long
using namespace std;
const int N = 2e3 + 10;
ll find_maximum(int k, vector < vector < int > > x) {
priority_queue < pair < int, int > > pq;
vector < pair < int, int > > p(N);
stack < int > st[N];
stack < int > a[N];
int n = x.size();
int m = x[0].size();
ll res = 0;
for(int i = 0; i < n; i++) {
p[i].second = i;
for(int j = m - 1; j >= m - k; j--) {
st[i].push(x[i][j]);
res += st[i].top();
}
for(int j = m - 1; j >= 0; j--) a[i].push(x[i][j]);
if(st[i].size() && a[i].size()) pq.push({- a[i].top() - st[i].top(), i});
}
vector < vector < int > > l(n, vector < int >());
vector < vector < int > > r(n, vector < int >());
for(int i = 0; i < n * k / 2; i++) {
int f = pq.top().first;
int s = pq.top().second;
pq.pop();
res += f;
p[s].first++;
st[s].pop();
a[s].pop();
if(st[s].size() && a[s].size()) pq.push({- a[s].top() - st[s].top(), s});
}
vector < vector < int > > vr(n, vector < int > (m, -1));
for(int i = 0; i < n; i++) {
for(int j = 0; j < p[i].first; j++) l[i].push_back(j);
for(int j = m - (k - p[i].first); j < m; j++) r[i].push_back(j);
}
for(int i = 0; i < k; i++) {
sort(p.rbegin(), p.rend());
for(int j = 0; j < n / 2; j++) {
vr[p[j].second][l[p[j].second].back()] = i;
p[j].first--;
l[p[j].second].pop_back();
}
for(int j = n / 2; j < n; j++) {
vr[p[j].second][r[p[j].second].back()] = i;
r[p[j].second].pop_back();
}
}
allocate_tickets(vr);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3052 KB |
Output is correct |
2 |
Correct |
2 ms |
3052 KB |
Output is correct |
3 |
Correct |
3 ms |
3180 KB |
Output is correct |
4 |
Correct |
3 ms |
3052 KB |
Output is correct |
5 |
Correct |
3 ms |
3180 KB |
Output is correct |
6 |
Correct |
4 ms |
3564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3180 KB |
Output is correct |
2 |
Correct |
2 ms |
3052 KB |
Output is correct |
3 |
Correct |
3 ms |
3180 KB |
Output is correct |
4 |
Correct |
5 ms |
3308 KB |
Output is correct |
5 |
Correct |
32 ms |
6508 KB |
Output is correct |
6 |
Correct |
682 ms |
64612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3052 KB |
Output is correct |
2 |
Correct |
2 ms |
3180 KB |
Output is correct |
3 |
Correct |
4 ms |
3052 KB |
Output is correct |
4 |
Correct |
6 ms |
3308 KB |
Output is correct |
5 |
Correct |
34 ms |
6116 KB |
Output is correct |
6 |
Correct |
737 ms |
75648 KB |
Output is correct |
7 |
Correct |
801 ms |
80612 KB |
Output is correct |
8 |
Correct |
9 ms |
3308 KB |
Output is correct |
9 |
Correct |
4 ms |
3052 KB |
Output is correct |
10 |
Correct |
3 ms |
3052 KB |
Output is correct |
11 |
Correct |
3 ms |
3052 KB |
Output is correct |
12 |
Correct |
16 ms |
3820 KB |
Output is correct |
13 |
Correct |
31 ms |
5356 KB |
Output is correct |
14 |
Correct |
38 ms |
5600 KB |
Output is correct |
15 |
Correct |
831 ms |
84836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3052 KB |
Output is correct |
2 |
Correct |
3 ms |
3052 KB |
Output is correct |
3 |
Correct |
3 ms |
3052 KB |
Output is correct |
4 |
Correct |
10 ms |
3308 KB |
Output is correct |
5 |
Correct |
50 ms |
7268 KB |
Output is correct |
6 |
Correct |
50 ms |
3680 KB |
Output is correct |
7 |
Correct |
11 ms |
3948 KB |
Output is correct |
8 |
Correct |
1142 ms |
88292 KB |
Output is correct |
9 |
Correct |
1055 ms |
81380 KB |
Output is correct |
10 |
Correct |
1046 ms |
80740 KB |
Output is correct |
11 |
Correct |
1141 ms |
86116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3052 KB |
Output is correct |
2 |
Correct |
5 ms |
3312 KB |
Output is correct |
3 |
Correct |
5 ms |
3308 KB |
Output is correct |
4 |
Correct |
5 ms |
3308 KB |
Output is correct |
5 |
Correct |
6 ms |
3308 KB |
Output is correct |
6 |
Correct |
7 ms |
3308 KB |
Output is correct |
7 |
Correct |
5 ms |
3052 KB |
Output is correct |
8 |
Correct |
3 ms |
3052 KB |
Output is correct |
9 |
Correct |
6 ms |
3308 KB |
Output is correct |
10 |
Correct |
7 ms |
3308 KB |
Output is correct |
11 |
Correct |
7 ms |
3308 KB |
Output is correct |
12 |
Correct |
7 ms |
3308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3052 KB |
Output is correct |
2 |
Correct |
5 ms |
3312 KB |
Output is correct |
3 |
Correct |
5 ms |
3308 KB |
Output is correct |
4 |
Correct |
5 ms |
3308 KB |
Output is correct |
5 |
Correct |
6 ms |
3308 KB |
Output is correct |
6 |
Correct |
7 ms |
3308 KB |
Output is correct |
7 |
Correct |
5 ms |
3052 KB |
Output is correct |
8 |
Correct |
3 ms |
3052 KB |
Output is correct |
9 |
Correct |
6 ms |
3308 KB |
Output is correct |
10 |
Correct |
7 ms |
3308 KB |
Output is correct |
11 |
Correct |
7 ms |
3308 KB |
Output is correct |
12 |
Correct |
7 ms |
3308 KB |
Output is correct |
13 |
Correct |
30 ms |
6372 KB |
Output is correct |
14 |
Correct |
31 ms |
6380 KB |
Output is correct |
15 |
Correct |
41 ms |
6500 KB |
Output is correct |
16 |
Correct |
49 ms |
7268 KB |
Output is correct |
17 |
Correct |
3 ms |
3180 KB |
Output is correct |
18 |
Correct |
6 ms |
3436 KB |
Output is correct |
19 |
Correct |
5 ms |
3180 KB |
Output is correct |
20 |
Correct |
37 ms |
5988 KB |
Output is correct |
21 |
Correct |
42 ms |
6372 KB |
Output is correct |
22 |
Correct |
46 ms |
6372 KB |
Output is correct |
23 |
Correct |
45 ms |
6756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3052 KB |
Output is correct |
2 |
Correct |
2 ms |
3052 KB |
Output is correct |
3 |
Correct |
3 ms |
3180 KB |
Output is correct |
4 |
Correct |
3 ms |
3052 KB |
Output is correct |
5 |
Correct |
3 ms |
3180 KB |
Output is correct |
6 |
Correct |
4 ms |
3564 KB |
Output is correct |
7 |
Correct |
4 ms |
3180 KB |
Output is correct |
8 |
Correct |
2 ms |
3052 KB |
Output is correct |
9 |
Correct |
3 ms |
3180 KB |
Output is correct |
10 |
Correct |
5 ms |
3308 KB |
Output is correct |
11 |
Correct |
32 ms |
6508 KB |
Output is correct |
12 |
Correct |
682 ms |
64612 KB |
Output is correct |
13 |
Correct |
3 ms |
3052 KB |
Output is correct |
14 |
Correct |
2 ms |
3180 KB |
Output is correct |
15 |
Correct |
4 ms |
3052 KB |
Output is correct |
16 |
Correct |
6 ms |
3308 KB |
Output is correct |
17 |
Correct |
34 ms |
6116 KB |
Output is correct |
18 |
Correct |
737 ms |
75648 KB |
Output is correct |
19 |
Correct |
801 ms |
80612 KB |
Output is correct |
20 |
Correct |
9 ms |
3308 KB |
Output is correct |
21 |
Correct |
4 ms |
3052 KB |
Output is correct |
22 |
Correct |
3 ms |
3052 KB |
Output is correct |
23 |
Correct |
3 ms |
3052 KB |
Output is correct |
24 |
Correct |
16 ms |
3820 KB |
Output is correct |
25 |
Correct |
31 ms |
5356 KB |
Output is correct |
26 |
Correct |
38 ms |
5600 KB |
Output is correct |
27 |
Correct |
831 ms |
84836 KB |
Output is correct |
28 |
Correct |
3 ms |
3052 KB |
Output is correct |
29 |
Correct |
3 ms |
3052 KB |
Output is correct |
30 |
Correct |
3 ms |
3052 KB |
Output is correct |
31 |
Correct |
10 ms |
3308 KB |
Output is correct |
32 |
Correct |
50 ms |
7268 KB |
Output is correct |
33 |
Correct |
50 ms |
3680 KB |
Output is correct |
34 |
Correct |
11 ms |
3948 KB |
Output is correct |
35 |
Correct |
1142 ms |
88292 KB |
Output is correct |
36 |
Correct |
1055 ms |
81380 KB |
Output is correct |
37 |
Correct |
1046 ms |
80740 KB |
Output is correct |
38 |
Correct |
1141 ms |
86116 KB |
Output is correct |
39 |
Correct |
2 ms |
3052 KB |
Output is correct |
40 |
Correct |
5 ms |
3312 KB |
Output is correct |
41 |
Correct |
5 ms |
3308 KB |
Output is correct |
42 |
Correct |
5 ms |
3308 KB |
Output is correct |
43 |
Correct |
6 ms |
3308 KB |
Output is correct |
44 |
Correct |
7 ms |
3308 KB |
Output is correct |
45 |
Correct |
5 ms |
3052 KB |
Output is correct |
46 |
Correct |
3 ms |
3052 KB |
Output is correct |
47 |
Correct |
6 ms |
3308 KB |
Output is correct |
48 |
Correct |
7 ms |
3308 KB |
Output is correct |
49 |
Correct |
7 ms |
3308 KB |
Output is correct |
50 |
Correct |
7 ms |
3308 KB |
Output is correct |
51 |
Correct |
30 ms |
6372 KB |
Output is correct |
52 |
Correct |
31 ms |
6380 KB |
Output is correct |
53 |
Correct |
41 ms |
6500 KB |
Output is correct |
54 |
Correct |
49 ms |
7268 KB |
Output is correct |
55 |
Correct |
3 ms |
3180 KB |
Output is correct |
56 |
Correct |
6 ms |
3436 KB |
Output is correct |
57 |
Correct |
5 ms |
3180 KB |
Output is correct |
58 |
Correct |
37 ms |
5988 KB |
Output is correct |
59 |
Correct |
42 ms |
6372 KB |
Output is correct |
60 |
Correct |
46 ms |
6372 KB |
Output is correct |
61 |
Correct |
45 ms |
6756 KB |
Output is correct |
62 |
Correct |
79 ms |
12004 KB |
Output is correct |
63 |
Correct |
79 ms |
12004 KB |
Output is correct |
64 |
Correct |
150 ms |
13544 KB |
Output is correct |
65 |
Correct |
412 ms |
42620 KB |
Output is correct |
66 |
Correct |
498 ms |
48868 KB |
Output is correct |
67 |
Correct |
10 ms |
3948 KB |
Output is correct |
68 |
Correct |
53 ms |
3688 KB |
Output is correct |
69 |
Correct |
693 ms |
64488 KB |
Output is correct |
70 |
Correct |
881 ms |
75836 KB |
Output is correct |
71 |
Correct |
1144 ms |
88172 KB |
Output is correct |
72 |
Correct |
965 ms |
89824 KB |
Output is correct |
73 |
Correct |
1066 ms |
82788 KB |
Output is correct |
74 |
Correct |
798 ms |
80868 KB |
Output is correct |
75 |
Correct |
869 ms |
73316 KB |
Output is correct |