// I can do all things through Christ who strengthens me
// Philippians 4:13
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = j; i < (k); i++)
#define RREP(i, j, k) for (int i = j; i >= (k); i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 1505;
int n, m, k;
vector<vi> x, s;
vi grp[MAXN][2];
ll ans;
int l[MAXN], r[MAXN];
priority_queue<ii> pq;
ll find_maximum(int _k, vector<vi> _x) {
k = _k; x = _x;
n = SZ(x); m = SZ(x[0]);
s = vector<vi>(n, vi(m, -1));
viii vx;
REP (i, 0, n) {
r[i] = m - k;
l[i] = 0;
REP (j, m - k, m) {
ans += x[i][j];
}
pq.push({-x[i][r[i]] - x[i][l[i]], i});
}
REP (z, 0, n / 2 * k) {
auto [v, i] = pq.top(); pq.pop();
ans += v;
r[i]++; l[i]++;
if (r[i] != m) {
pq.push({-x[i][r[i]] - x[i][l[i]], i});
}
}
REP (i, 0, n) {
REP (j, 0, l[i]) {
grp[i][0].pb(j);
}
REP (j, r[i], m) {
grp[i][1].pb(j);
}
}
REP (z, 0, k) {
int cnt[2] = {0, 0};
REP (i, 0, n) {
if (grp[i][0].empty()) {
cnt[1]++;
int j = grp[i][1].back(); grp[i][1].pop_back();
s[i][j] = z;
} else if (grp[i][1].empty()) {
cnt[0]++;
int j = grp[i][0].back(); grp[i][0].pop_back();
s[i][j] = z;
}
}
REP (i, 0, n) {
if (grp[i][0].empty() || grp[i][1].empty()) {
continue;
}
REP (l, 0, 2) {
if (cnt[l] == n / 2) {
continue;
}
cnt[l]++;
int j = grp[i][l].back(); grp[i][l].pop_back();
s[i][j] = z;
break;
}
}
}
allocate_tickets(s);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
2772 KB |
Output is correct |
6 |
Correct |
391 ms |
60352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
15 ms |
3096 KB |
Output is correct |
6 |
Correct |
372 ms |
67384 KB |
Output is correct |
7 |
Correct |
392 ms |
70672 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
5 ms |
980 KB |
Output is correct |
13 |
Correct |
13 ms |
2704 KB |
Output is correct |
14 |
Correct |
13 ms |
2760 KB |
Output is correct |
15 |
Correct |
415 ms |
72404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
20 ms |
3376 KB |
Output is correct |
6 |
Correct |
3 ms |
852 KB |
Output is correct |
7 |
Correct |
4 ms |
1108 KB |
Output is correct |
8 |
Correct |
528 ms |
75268 KB |
Output is correct |
9 |
Correct |
497 ms |
70884 KB |
Output is correct |
10 |
Correct |
500 ms |
70216 KB |
Output is correct |
11 |
Correct |
536 ms |
75160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 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 |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 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 |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
596 KB |
Output is correct |
13 |
Correct |
17 ms |
2732 KB |
Output is correct |
14 |
Correct |
17 ms |
2832 KB |
Output is correct |
15 |
Correct |
18 ms |
3028 KB |
Output is correct |
16 |
Correct |
23 ms |
3364 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
17 ms |
3020 KB |
Output is correct |
21 |
Correct |
18 ms |
3076 KB |
Output is correct |
22 |
Correct |
18 ms |
3176 KB |
Output is correct |
23 |
Correct |
18 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
16 ms |
2772 KB |
Output is correct |
12 |
Correct |
391 ms |
60352 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
15 ms |
3096 KB |
Output is correct |
18 |
Correct |
372 ms |
67384 KB |
Output is correct |
19 |
Correct |
392 ms |
70672 KB |
Output is correct |
20 |
Correct |
2 ms |
596 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
5 ms |
980 KB |
Output is correct |
25 |
Correct |
13 ms |
2704 KB |
Output is correct |
26 |
Correct |
13 ms |
2760 KB |
Output is correct |
27 |
Correct |
415 ms |
72404 KB |
Output is correct |
28 |
Correct |
0 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
596 KB |
Output is correct |
32 |
Correct |
20 ms |
3376 KB |
Output is correct |
33 |
Correct |
3 ms |
852 KB |
Output is correct |
34 |
Correct |
4 ms |
1108 KB |
Output is correct |
35 |
Correct |
528 ms |
75268 KB |
Output is correct |
36 |
Correct |
497 ms |
70884 KB |
Output is correct |
37 |
Correct |
500 ms |
70216 KB |
Output is correct |
38 |
Correct |
536 ms |
75160 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
468 KB |
Output is correct |
41 |
Correct |
1 ms |
468 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 |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
2 ms |
468 KB |
Output is correct |
48 |
Correct |
2 ms |
468 KB |
Output is correct |
49 |
Correct |
2 ms |
468 KB |
Output is correct |
50 |
Correct |
2 ms |
596 KB |
Output is correct |
51 |
Correct |
17 ms |
2732 KB |
Output is correct |
52 |
Correct |
17 ms |
2832 KB |
Output is correct |
53 |
Correct |
18 ms |
3028 KB |
Output is correct |
54 |
Correct |
23 ms |
3364 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
2 ms |
596 KB |
Output is correct |
57 |
Correct |
1 ms |
468 KB |
Output is correct |
58 |
Correct |
17 ms |
3020 KB |
Output is correct |
59 |
Correct |
18 ms |
3076 KB |
Output is correct |
60 |
Correct |
18 ms |
3176 KB |
Output is correct |
61 |
Correct |
18 ms |
3156 KB |
Output is correct |
62 |
Correct |
43 ms |
7032 KB |
Output is correct |
63 |
Correct |
49 ms |
7180 KB |
Output is correct |
64 |
Correct |
53 ms |
8528 KB |
Output is correct |
65 |
Correct |
196 ms |
30008 KB |
Output is correct |
66 |
Correct |
239 ms |
32728 KB |
Output is correct |
67 |
Correct |
5 ms |
1108 KB |
Output is correct |
68 |
Correct |
3 ms |
852 KB |
Output is correct |
69 |
Correct |
388 ms |
60468 KB |
Output is correct |
70 |
Correct |
458 ms |
67404 KB |
Output is correct |
71 |
Correct |
517 ms |
75216 KB |
Output is correct |
72 |
Correct |
466 ms |
72816 KB |
Output is correct |
73 |
Correct |
495 ms |
72388 KB |
Output is correct |
74 |
Correct |
402 ms |
65456 KB |
Output is correct |
75 |
Correct |
460 ms |
65436 KB |
Output is correct |