#include "tickets.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 1500;
const int INF = 1e18;
struct Ayaya {
int val, i, j;
Ayaya(int _val, int _i, int _j): val(_val), i(_i), j(_j) {}
bool operator<(const Ayaya &rhs) const {
return val < rhs.val;
}
bool operator>(const Ayaya &rhs) const {
return val > rhs.val;
}
};
int find_maximum(i32 _k, vector<vector<i32>> x) {
int k = _k;
int n = sz(x);
int m = sz(x[0]);
vector<vector<i32>> answer(n, vector<i32>(m, -1));
vector<vector<int>> cost(n, vector<int>(k + 1, 0));
int tot = 0;
For(i, 0, n - 1) {
For(j, 0, k - 1) cost[i][0] -= x[i][j];
For(j, 1, k) cost[i][j] = cost[i][j - 1] + x[i][k - j] + x[i][m - j];
tot += cost[i][k];
Forr(j, k, 1) cost[i][j] -= cost[i][j - 1];
}
vector<int> le(n, k), ri(n);
priority_queue<Ayaya> pq;
For(i, 0, n - 1) {
pq.emplace(-cost[i][k], i, k - 1);
}
For(_, 1, n * k / 2) {
auto aya = pq.top(); pq.pop();
tot += aya.val;
le[aya.i] = aya.j;
if(aya.j > 0) {
pq.emplace(-cost[aya.i][aya.j], aya.i, aya.j - 1);
}
}
For(i, 0, n - 1) {
ri[i] = m - le[i];
le[i] = k - le[i] - 1;
}
// contruct answer
For(i, 0, k - 1) {
int cl = n / 2, cr = n / 2;
vector<int> vis(n, 0);
For(j, 0, n - 1) {
if(le[j] < 0) {
answer[j][ri[j]] = (i32) i;
ri[j]++;
cr--;
vis[j] = 1;
} else if(ri[j] >= m) {
answer[j][le[j]] = (i32) i;
le[j]--;
cl--;
vis[j] = 1;
}
}
For(j, 0, n - 1) if(!vis[j]) {
if(cl) {
answer[j][le[j]] = (i32) i;
le[j]--;
cl--;
} else {
answer[j][ri[j]] = (i32) i;
ri[j]++;
cr--;
}
}
}
allocate_tickets(answer);
return tot;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
4 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
440 KB |
Output is correct |
5 |
Correct |
18 ms |
3156 KB |
Output is correct |
6 |
Correct |
471 ms |
52100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
17 ms |
2908 KB |
Output is correct |
6 |
Correct |
397 ms |
65584 KB |
Output is correct |
7 |
Correct |
416 ms |
68940 KB |
Output is correct |
8 |
Correct |
3 ms |
596 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
300 KB |
Output is correct |
12 |
Correct |
5 ms |
980 KB |
Output is correct |
13 |
Correct |
14 ms |
2620 KB |
Output is correct |
14 |
Correct |
14 ms |
2644 KB |
Output is correct |
15 |
Correct |
426 ms |
71900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
572 KB |
Output is correct |
5 |
Correct |
22 ms |
3336 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
5 ms |
1168 KB |
Output is correct |
8 |
Correct |
564 ms |
75716 KB |
Output is correct |
9 |
Correct |
528 ms |
87436 KB |
Output is correct |
10 |
Correct |
522 ms |
87556 KB |
Output is correct |
11 |
Correct |
556 ms |
93768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 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 |
212 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 |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 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 |
212 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 |
468 KB |
Output is correct |
13 |
Correct |
18 ms |
2368 KB |
Output is correct |
14 |
Correct |
18 ms |
2328 KB |
Output is correct |
15 |
Correct |
20 ms |
2752 KB |
Output is correct |
16 |
Correct |
23 ms |
3148 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
17 ms |
2776 KB |
Output is correct |
21 |
Correct |
20 ms |
2764 KB |
Output is correct |
22 |
Correct |
19 ms |
2924 KB |
Output is correct |
23 |
Correct |
20 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
824 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
4 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
440 KB |
Output is correct |
11 |
Correct |
18 ms |
3156 KB |
Output is correct |
12 |
Correct |
471 ms |
52100 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
300 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
17 ms |
2908 KB |
Output is correct |
18 |
Correct |
397 ms |
65584 KB |
Output is correct |
19 |
Correct |
416 ms |
68940 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
300 KB |
Output is correct |
24 |
Correct |
5 ms |
980 KB |
Output is correct |
25 |
Correct |
14 ms |
2620 KB |
Output is correct |
26 |
Correct |
14 ms |
2644 KB |
Output is correct |
27 |
Correct |
426 ms |
71900 KB |
Output is correct |
28 |
Correct |
1 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 |
572 KB |
Output is correct |
32 |
Correct |
22 ms |
3336 KB |
Output is correct |
33 |
Correct |
4 ms |
852 KB |
Output is correct |
34 |
Correct |
5 ms |
1168 KB |
Output is correct |
35 |
Correct |
564 ms |
75716 KB |
Output is correct |
36 |
Correct |
528 ms |
87436 KB |
Output is correct |
37 |
Correct |
522 ms |
87556 KB |
Output is correct |
38 |
Correct |
556 ms |
93768 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
2 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 |
212 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 |
468 KB |
Output is correct |
51 |
Correct |
18 ms |
2368 KB |
Output is correct |
52 |
Correct |
18 ms |
2328 KB |
Output is correct |
53 |
Correct |
20 ms |
2752 KB |
Output is correct |
54 |
Correct |
23 ms |
3148 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
2 ms |
468 KB |
Output is correct |
57 |
Correct |
1 ms |
340 KB |
Output is correct |
58 |
Correct |
17 ms |
2776 KB |
Output is correct |
59 |
Correct |
20 ms |
2764 KB |
Output is correct |
60 |
Correct |
19 ms |
2924 KB |
Output is correct |
61 |
Correct |
20 ms |
3028 KB |
Output is correct |
62 |
Correct |
49 ms |
8376 KB |
Output is correct |
63 |
Correct |
50 ms |
8464 KB |
Output is correct |
64 |
Correct |
58 ms |
10584 KB |
Output is correct |
65 |
Correct |
218 ms |
37040 KB |
Output is correct |
66 |
Correct |
237 ms |
41464 KB |
Output is correct |
67 |
Correct |
5 ms |
1236 KB |
Output is correct |
68 |
Correct |
4 ms |
884 KB |
Output is correct |
69 |
Correct |
430 ms |
73296 KB |
Output is correct |
70 |
Correct |
481 ms |
83020 KB |
Output is correct |
71 |
Correct |
560 ms |
93620 KB |
Output is correct |
72 |
Correct |
472 ms |
77072 KB |
Output is correct |
73 |
Correct |
545 ms |
89224 KB |
Output is correct |
74 |
Correct |
424 ms |
68444 KB |
Output is correct |
75 |
Correct |
494 ms |
80924 KB |
Output is correct |