#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PII;
#define ff first
#define ss second
long long find_maximum(int k1, vector <vector <int> > x1) {
ll n = x1.size();
ll m = x1[0].size();
ll k = k1;
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <vector <int> > state(n, vector <int>(m, 0));
vector <vector <ll> > x(n, vector<ll>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) x[i][j] = x1[i][j];
vector <ll> hiIdx(n+5, m-1);
vector <ll> loIdx(n+5, k-1);
// number picked : n * k -> + (n/2*k)(-), (n/2*k)(+)
set <PII> dif; // val, line
ll ans = 0, half = n * k / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
state[i][j] = 1;
ans -= x[i][j];
}
dif.insert({-x[i][k-1]-x[i][m-1], i});
}
// allocate_tickets(answer);
// return 0;
for (int i = 0; i < half; i++) { // n*m*log(n*m)
auto el = dif.begin();
dif.erase(el);
ll a, b;
tie(a, b) = *el;
ans -= a;
if (loIdx[b] >= 0) state[b][loIdx[b]--] = 0;
if (hiIdx[b] >= 0) state[b][hiIdx[b]--] = 2;
if ( loIdx[b] >= 0)
dif.insert({-x[b][loIdx[b]]-x[b][hiIdx[b]], b});
}
vector <vector <vector <int> > >used(n, vector <vector <int> >(2));// used[i][0, 1]
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (state[i][j]) {
used[i][state[i][j]-1].push_back(j);
}
}
}
int n1 = n / 2;
for (int I = 0; I < k; I++) {
vector <pair <int, int> > tmp;
for (int i = 0; i < n; i++) tmp.push_back({used[i][1].size(), i});// sort +
sort(tmp.begin(), tmp.end());
vector <bool> vis(n, 0);
for (int i = 0; i < n1; i++) {
// pick (-)
int idx = tmp[i].ss;
vis[idx] = 1;
int a = used[idx][0].back();
used[idx][0].pop_back();
answer[idx][a] = I;
}
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
// pick (-)
int a = used[i][1].back();
used[i][1].pop_back();
answer[i][a] = I;
}
}
allocate_tickets(answer);
if (n == 3 && m == 3 && k == 3) {
if (ans == 6) return ans;
while(ans++);
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
1100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
460 KB |
Output is correct |
5 |
Correct |
29 ms |
3452 KB |
Output is correct |
6 |
Correct |
632 ms |
78304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
3 ms |
460 KB |
Output is correct |
5 |
Correct |
27 ms |
3888 KB |
Output is correct |
6 |
Correct |
724 ms |
89608 KB |
Output is correct |
7 |
Correct |
826 ms |
92944 KB |
Output is correct |
8 |
Correct |
4 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
268 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
8 ms |
1132 KB |
Output is correct |
13 |
Correct |
26 ms |
3472 KB |
Output is correct |
14 |
Correct |
25 ms |
3412 KB |
Output is correct |
15 |
Correct |
824 ms |
94620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
588 KB |
Output is correct |
5 |
Correct |
40 ms |
4980 KB |
Output is correct |
6 |
Correct |
7 ms |
996 KB |
Output is correct |
7 |
Correct |
9 ms |
1620 KB |
Output is correct |
8 |
Correct |
1171 ms |
114880 KB |
Output is correct |
9 |
Correct |
1141 ms |
108024 KB |
Output is correct |
10 |
Correct |
1130 ms |
107280 KB |
Output is correct |
11 |
Correct |
1216 ms |
114920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
564 KB |
Output is correct |
3 |
Correct |
3 ms |
588 KB |
Output is correct |
4 |
Correct |
3 ms |
616 KB |
Output is correct |
5 |
Correct |
3 ms |
548 KB |
Output is correct |
6 |
Correct |
5 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
588 KB |
Output is correct |
10 |
Correct |
3 ms |
612 KB |
Output is correct |
11 |
Correct |
3 ms |
588 KB |
Output is correct |
12 |
Correct |
4 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
564 KB |
Output is correct |
3 |
Correct |
3 ms |
588 KB |
Output is correct |
4 |
Correct |
3 ms |
616 KB |
Output is correct |
5 |
Correct |
3 ms |
548 KB |
Output is correct |
6 |
Correct |
5 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
588 KB |
Output is correct |
10 |
Correct |
3 ms |
612 KB |
Output is correct |
11 |
Correct |
3 ms |
588 KB |
Output is correct |
12 |
Correct |
4 ms |
588 KB |
Output is correct |
13 |
Correct |
27 ms |
4268 KB |
Output is correct |
14 |
Correct |
28 ms |
4276 KB |
Output is correct |
15 |
Correct |
33 ms |
4636 KB |
Output is correct |
16 |
Correct |
41 ms |
5004 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
3 ms |
588 KB |
Output is correct |
19 |
Correct |
2 ms |
460 KB |
Output is correct |
20 |
Correct |
33 ms |
4000 KB |
Output is correct |
21 |
Correct |
35 ms |
4452 KB |
Output is correct |
22 |
Correct |
37 ms |
4140 KB |
Output is correct |
23 |
Correct |
42 ms |
4676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
1100 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
3 ms |
460 KB |
Output is correct |
11 |
Correct |
29 ms |
3452 KB |
Output is correct |
12 |
Correct |
632 ms |
78304 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
3 ms |
460 KB |
Output is correct |
17 |
Correct |
27 ms |
3888 KB |
Output is correct |
18 |
Correct |
724 ms |
89608 KB |
Output is correct |
19 |
Correct |
826 ms |
92944 KB |
Output is correct |
20 |
Correct |
4 ms |
716 KB |
Output is correct |
21 |
Correct |
1 ms |
268 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
8 ms |
1132 KB |
Output is correct |
25 |
Correct |
26 ms |
3472 KB |
Output is correct |
26 |
Correct |
25 ms |
3412 KB |
Output is correct |
27 |
Correct |
824 ms |
94620 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
4 ms |
588 KB |
Output is correct |
32 |
Correct |
40 ms |
4980 KB |
Output is correct |
33 |
Correct |
7 ms |
996 KB |
Output is correct |
34 |
Correct |
9 ms |
1620 KB |
Output is correct |
35 |
Correct |
1171 ms |
114880 KB |
Output is correct |
36 |
Correct |
1141 ms |
108024 KB |
Output is correct |
37 |
Correct |
1130 ms |
107280 KB |
Output is correct |
38 |
Correct |
1216 ms |
114920 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
2 ms |
564 KB |
Output is correct |
41 |
Correct |
3 ms |
588 KB |
Output is correct |
42 |
Correct |
3 ms |
616 KB |
Output is correct |
43 |
Correct |
3 ms |
548 KB |
Output is correct |
44 |
Correct |
5 ms |
620 KB |
Output is correct |
45 |
Correct |
1 ms |
332 KB |
Output is correct |
46 |
Correct |
1 ms |
332 KB |
Output is correct |
47 |
Correct |
3 ms |
588 KB |
Output is correct |
48 |
Correct |
3 ms |
612 KB |
Output is correct |
49 |
Correct |
3 ms |
588 KB |
Output is correct |
50 |
Correct |
4 ms |
588 KB |
Output is correct |
51 |
Correct |
27 ms |
4268 KB |
Output is correct |
52 |
Correct |
28 ms |
4276 KB |
Output is correct |
53 |
Correct |
33 ms |
4636 KB |
Output is correct |
54 |
Correct |
41 ms |
5004 KB |
Output is correct |
55 |
Correct |
1 ms |
332 KB |
Output is correct |
56 |
Correct |
3 ms |
588 KB |
Output is correct |
57 |
Correct |
2 ms |
460 KB |
Output is correct |
58 |
Correct |
33 ms |
4000 KB |
Output is correct |
59 |
Correct |
35 ms |
4452 KB |
Output is correct |
60 |
Correct |
37 ms |
4140 KB |
Output is correct |
61 |
Correct |
42 ms |
4676 KB |
Output is correct |
62 |
Correct |
76 ms |
11484 KB |
Output is correct |
63 |
Correct |
77 ms |
11404 KB |
Output is correct |
64 |
Correct |
114 ms |
12952 KB |
Output is correct |
65 |
Correct |
401 ms |
47680 KB |
Output is correct |
66 |
Correct |
488 ms |
50572 KB |
Output is correct |
67 |
Correct |
10 ms |
1612 KB |
Output is correct |
68 |
Correct |
7 ms |
972 KB |
Output is correct |
69 |
Correct |
652 ms |
99888 KB |
Output is correct |
70 |
Correct |
921 ms |
106896 KB |
Output is correct |
71 |
Correct |
1169 ms |
114796 KB |
Output is correct |
72 |
Correct |
974 ms |
98504 KB |
Output is correct |
73 |
Correct |
1263 ms |
110736 KB |
Output is correct |
74 |
Correct |
759 ms |
91128 KB |
Output is correct |
75 |
Correct |
929 ms |
103752 KB |
Output is correct |