#include "tickets.h"
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1501;
int type[mxN][mxN];
int lev[mxN];
ll find_maximum(int k, vector<vector<int>> arr) {
int n = arr.size();
int m = arr[0].size();
vector<vector<int>> s(n, vector<int>(m, -1));
ll res = 0;
priority_queue<ttgl, vector<ttgl>, greater<ttgl>> pq;
owo(i, 0, n) {
sort(arr[i].begin(), arr[i].end());
pq.push({arr[i][0] + arr[i][m-k], i});
lev[i] = 0;
owo(j, 0, k) {
res += arr[i][m-j-1];
type[i][m-j-1] = 1;
}
}
owo(_, 0, n*k/2) {
auto p = pq.top();
pq.pop();
res -= p.first;
type[p.second][m-k+lev[p.second]] = 0;
type[p.second][lev[p.second]] = -1;
lev[p.second]++;
if(lev[p.second] < k) pq.push({arr[p.second][lev[p.second]] + arr[p.second][m-k+lev[p.second]], p.second});
}
vector<vector<int>> pos(n);
vector<vector<int>> neg(n);
owo(i, 0, n) {
owo(j, 0, m) {
if(type[i][j]==1)pos[i].senpai(j);
else if(type[i][j]==-1)neg[i].senpai(j);
}
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
owo(col, 0, k) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
return pos[a].size() < pos[b].size();
});
owo(i, 0, n/2) {
int x = ord[i];
int y = ord[n-i-1];
s[x][neg[x].back()] = col;
neg[x].pop_back();
s[y][pos[y].back()] = col;
pos[y].pop_back();
}
}
allocate_tickets(s);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
1484 KB |
Output is correct |
6 |
Correct |
5 ms |
6732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
26 ms |
3692 KB |
Output is correct |
6 |
Correct |
628 ms |
57588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
716 KB |
Output is correct |
5 |
Correct |
26 ms |
4312 KB |
Output is correct |
6 |
Correct |
666 ms |
71808 KB |
Output is correct |
7 |
Correct |
758 ms |
75052 KB |
Output is correct |
8 |
Correct |
4 ms |
972 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
7 ms |
1640 KB |
Output is correct |
13 |
Correct |
23 ms |
4724 KB |
Output is correct |
14 |
Correct |
24 ms |
3396 KB |
Output is correct |
15 |
Correct |
739 ms |
76696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
35 ms |
5380 KB |
Output is correct |
6 |
Correct |
6 ms |
844 KB |
Output is correct |
7 |
Correct |
10 ms |
7256 KB |
Output is correct |
8 |
Correct |
971 ms |
96956 KB |
Output is correct |
9 |
Correct |
953 ms |
92004 KB |
Output is correct |
10 |
Correct |
900 ms |
90500 KB |
Output is correct |
11 |
Correct |
969 ms |
97092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
844 KB |
Output is correct |
3 |
Correct |
4 ms |
816 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
4 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
4 ms |
864 KB |
Output is correct |
10 |
Correct |
3 ms |
844 KB |
Output is correct |
11 |
Correct |
3 ms |
844 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
844 KB |
Output is correct |
3 |
Correct |
4 ms |
816 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
5 |
Correct |
4 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
4 ms |
864 KB |
Output is correct |
10 |
Correct |
3 ms |
844 KB |
Output is correct |
11 |
Correct |
3 ms |
844 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
26 ms |
4664 KB |
Output is correct |
14 |
Correct |
28 ms |
4744 KB |
Output is correct |
15 |
Correct |
32 ms |
5068 KB |
Output is correct |
16 |
Correct |
35 ms |
5412 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
1740 KB |
Output is correct |
19 |
Correct |
2 ms |
1612 KB |
Output is correct |
20 |
Correct |
29 ms |
4436 KB |
Output is correct |
21 |
Correct |
32 ms |
5044 KB |
Output is correct |
22 |
Correct |
34 ms |
4708 KB |
Output is correct |
23 |
Correct |
34 ms |
5080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
1484 KB |
Output is correct |
6 |
Correct |
5 ms |
6732 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
716 KB |
Output is correct |
11 |
Correct |
26 ms |
3692 KB |
Output is correct |
12 |
Correct |
628 ms |
57588 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
716 KB |
Output is correct |
17 |
Correct |
26 ms |
4312 KB |
Output is correct |
18 |
Correct |
666 ms |
71808 KB |
Output is correct |
19 |
Correct |
758 ms |
75052 KB |
Output is correct |
20 |
Correct |
4 ms |
972 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
300 KB |
Output is correct |
23 |
Correct |
1 ms |
300 KB |
Output is correct |
24 |
Correct |
7 ms |
1640 KB |
Output is correct |
25 |
Correct |
23 ms |
4724 KB |
Output is correct |
26 |
Correct |
24 ms |
3396 KB |
Output is correct |
27 |
Correct |
739 ms |
76696 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
296 KB |
Output is correct |
30 |
Correct |
1 ms |
300 KB |
Output is correct |
31 |
Correct |
3 ms |
844 KB |
Output is correct |
32 |
Correct |
35 ms |
5380 KB |
Output is correct |
33 |
Correct |
6 ms |
844 KB |
Output is correct |
34 |
Correct |
10 ms |
7256 KB |
Output is correct |
35 |
Correct |
971 ms |
96956 KB |
Output is correct |
36 |
Correct |
953 ms |
92004 KB |
Output is correct |
37 |
Correct |
900 ms |
90500 KB |
Output is correct |
38 |
Correct |
969 ms |
97092 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
3 ms |
844 KB |
Output is correct |
41 |
Correct |
4 ms |
816 KB |
Output is correct |
42 |
Correct |
3 ms |
844 KB |
Output is correct |
43 |
Correct |
4 ms |
844 KB |
Output is correct |
44 |
Correct |
3 ms |
844 KB |
Output is correct |
45 |
Correct |
1 ms |
332 KB |
Output is correct |
46 |
Correct |
1 ms |
588 KB |
Output is correct |
47 |
Correct |
4 ms |
864 KB |
Output is correct |
48 |
Correct |
3 ms |
844 KB |
Output is correct |
49 |
Correct |
3 ms |
844 KB |
Output is correct |
50 |
Correct |
3 ms |
844 KB |
Output is correct |
51 |
Correct |
26 ms |
4664 KB |
Output is correct |
52 |
Correct |
28 ms |
4744 KB |
Output is correct |
53 |
Correct |
32 ms |
5068 KB |
Output is correct |
54 |
Correct |
35 ms |
5412 KB |
Output is correct |
55 |
Correct |
1 ms |
332 KB |
Output is correct |
56 |
Correct |
3 ms |
1740 KB |
Output is correct |
57 |
Correct |
2 ms |
1612 KB |
Output is correct |
58 |
Correct |
29 ms |
4436 KB |
Output is correct |
59 |
Correct |
32 ms |
5044 KB |
Output is correct |
60 |
Correct |
34 ms |
4708 KB |
Output is correct |
61 |
Correct |
34 ms |
5080 KB |
Output is correct |
62 |
Correct |
74 ms |
11144 KB |
Output is correct |
63 |
Correct |
76 ms |
11352 KB |
Output is correct |
64 |
Correct |
98 ms |
12868 KB |
Output is correct |
65 |
Correct |
347 ms |
41584 KB |
Output is correct |
66 |
Correct |
421 ms |
44360 KB |
Output is correct |
67 |
Correct |
10 ms |
7244 KB |
Output is correct |
68 |
Correct |
6 ms |
840 KB |
Output is correct |
69 |
Correct |
638 ms |
79520 KB |
Output is correct |
70 |
Correct |
813 ms |
89040 KB |
Output is correct |
71 |
Correct |
1068 ms |
96996 KB |
Output is correct |
72 |
Correct |
860 ms |
81504 KB |
Output is correct |
73 |
Correct |
898 ms |
93508 KB |
Output is correct |
74 |
Correct |
745 ms |
74116 KB |
Output is correct |
75 |
Correct |
789 ms |
86432 KB |
Output is correct |