#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7;
void allocate_tickets(vector<vi> s);
ll find_maximum(int k, vector<vi> x){
int n = x.size(), m = x[0].size(); ll ans = 0;
vector<vi> s(n, vi(m, -1)); vi f(n, 0), r(n, k-1);
vector<pi> p;
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
ans -= x[i][j];
p.pb({x[i][j] + x[i][m-k+j], i});
}
}
sort(p.begin(), p.end(), greater<pi>());
for(int i=0, tot=n*k/2; i<tot; i++){
ans += p[i].f; f[p[i].s]++; r[p[i].s]--;
}
for(int i=0, cnt=0; i<k; i++, cnt=0){
for(int j=0; j<n; j++){
if(!f[j]) {
s[j][r[j]] = i; r[j]--;
} else if(r[j] == -1) {
s[j][m - f[j]] = i; f[j]--; cnt++;
}
}
for(int j=0; j<n; j++){
if(f[j] && r[j]!=-1){
if(cnt < n/2) { s[j][m - f[j]] = i; f[j]--; cnt++; }
else { s[j][r[j]] = i; r[j]--; }
}
}
}
allocate_tickets(s); return ans;
}
//void allocate_tickets(vector<vi> s){
// for(int i=0; i<s.size(); i++){
// for(int x: s[i]) cout << x << " ";
// cout << endl;
// }
//}
//int main(){
// vector<vi> a = {{5, 9}, {1, 4}, {3, 6}, {2, 7}};
// cout << find_maximum(1, a) << endl;
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
32 ms |
2464 KB |
Output is correct |
6 |
Correct |
767 ms |
51480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
26 ms |
2552 KB |
Output is correct |
6 |
Correct |
700 ms |
53576 KB |
Output is correct |
7 |
Correct |
658 ms |
56468 KB |
Output is correct |
8 |
Correct |
4 ms |
640 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
7 ms |
904 KB |
Output is correct |
13 |
Correct |
22 ms |
2296 KB |
Output is correct |
14 |
Correct |
23 ms |
2300 KB |
Output is correct |
15 |
Correct |
659 ms |
58824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
512 KB |
Output is correct |
5 |
Correct |
42 ms |
2796 KB |
Output is correct |
6 |
Correct |
7 ms |
768 KB |
Output is correct |
7 |
Correct |
9 ms |
1024 KB |
Output is correct |
8 |
Correct |
1039 ms |
62304 KB |
Output is correct |
9 |
Correct |
955 ms |
58264 KB |
Output is correct |
10 |
Correct |
949 ms |
58212 KB |
Output is correct |
11 |
Correct |
1025 ms |
62372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
4 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
3 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
3 ms |
512 KB |
Output is correct |
6 |
Correct |
4 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
512 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
31 ms |
2420 KB |
Output is correct |
14 |
Correct |
32 ms |
2424 KB |
Output is correct |
15 |
Correct |
37 ms |
2584 KB |
Output is correct |
16 |
Correct |
41 ms |
2796 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
3 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
30 ms |
2552 KB |
Output is correct |
21 |
Correct |
35 ms |
2672 KB |
Output is correct |
22 |
Correct |
35 ms |
2796 KB |
Output is correct |
23 |
Correct |
38 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
3 ms |
512 KB |
Output is correct |
11 |
Correct |
32 ms |
2464 KB |
Output is correct |
12 |
Correct |
767 ms |
51480 KB |
Output is correct |
13 |
Correct |
1 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
26 ms |
2552 KB |
Output is correct |
18 |
Correct |
700 ms |
53576 KB |
Output is correct |
19 |
Correct |
658 ms |
56468 KB |
Output is correct |
20 |
Correct |
4 ms |
640 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Correct |
1 ms |
256 KB |
Output is correct |
24 |
Correct |
7 ms |
904 KB |
Output is correct |
25 |
Correct |
22 ms |
2296 KB |
Output is correct |
26 |
Correct |
23 ms |
2300 KB |
Output is correct |
27 |
Correct |
659 ms |
58824 KB |
Output is correct |
28 |
Correct |
1 ms |
256 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
3 ms |
512 KB |
Output is correct |
32 |
Correct |
42 ms |
2796 KB |
Output is correct |
33 |
Correct |
7 ms |
768 KB |
Output is correct |
34 |
Correct |
9 ms |
1024 KB |
Output is correct |
35 |
Correct |
1039 ms |
62304 KB |
Output is correct |
36 |
Correct |
955 ms |
58264 KB |
Output is correct |
37 |
Correct |
949 ms |
58212 KB |
Output is correct |
38 |
Correct |
1025 ms |
62372 KB |
Output is correct |
39 |
Correct |
0 ms |
256 KB |
Output is correct |
40 |
Correct |
3 ms |
512 KB |
Output is correct |
41 |
Correct |
3 ms |
512 KB |
Output is correct |
42 |
Correct |
4 ms |
512 KB |
Output is correct |
43 |
Correct |
3 ms |
512 KB |
Output is correct |
44 |
Correct |
4 ms |
512 KB |
Output is correct |
45 |
Correct |
1 ms |
384 KB |
Output is correct |
46 |
Correct |
1 ms |
384 KB |
Output is correct |
47 |
Correct |
3 ms |
512 KB |
Output is correct |
48 |
Correct |
3 ms |
512 KB |
Output is correct |
49 |
Correct |
3 ms |
512 KB |
Output is correct |
50 |
Correct |
3 ms |
512 KB |
Output is correct |
51 |
Correct |
31 ms |
2420 KB |
Output is correct |
52 |
Correct |
32 ms |
2424 KB |
Output is correct |
53 |
Correct |
37 ms |
2584 KB |
Output is correct |
54 |
Correct |
41 ms |
2796 KB |
Output is correct |
55 |
Correct |
1 ms |
384 KB |
Output is correct |
56 |
Correct |
3 ms |
512 KB |
Output is correct |
57 |
Correct |
2 ms |
384 KB |
Output is correct |
58 |
Correct |
30 ms |
2552 KB |
Output is correct |
59 |
Correct |
35 ms |
2672 KB |
Output is correct |
60 |
Correct |
35 ms |
2796 KB |
Output is correct |
61 |
Correct |
38 ms |
2668 KB |
Output is correct |
62 |
Correct |
88 ms |
6008 KB |
Output is correct |
63 |
Correct |
87 ms |
6136 KB |
Output is correct |
64 |
Correct |
110 ms |
7232 KB |
Output is correct |
65 |
Correct |
395 ms |
24036 KB |
Output is correct |
66 |
Correct |
448 ms |
27860 KB |
Output is correct |
67 |
Correct |
8 ms |
1024 KB |
Output is correct |
68 |
Correct |
7 ms |
768 KB |
Output is correct |
69 |
Correct |
764 ms |
51664 KB |
Output is correct |
70 |
Correct |
897 ms |
53536 KB |
Output is correct |
71 |
Correct |
1071 ms |
62500 KB |
Output is correct |
72 |
Correct |
854 ms |
59672 KB |
Output is correct |
73 |
Correct |
959 ms |
59072 KB |
Output is correct |
74 |
Correct |
723 ms |
52540 KB |
Output is correct |
75 |
Correct |
864 ms |
52320 KB |
Output is correct |