#include "tickets.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<lint, lint>;
const int MAXN = 1505;
struct node{
int x, y, v;
bool operator<(const node &n)const{
if(v != n.v) return v < n.v;
return y > n.y;
}
};
void BACKTRACK(vector<vector<int>> B, int k){
deque<int> dq[MAXN];
int bcnt[MAXN] = {};
for(int i=0; i<sz(B); i++){
for(auto &j : B[i]){
if(j > 0) bcnt[i]++;
}
for(int j=0; j<sz(B[i]); j++){
if(B[i][j] == -1) dq[i].push_back(j);
}
for(int j=0; j<sz(B[i]); j++){
if(B[i][j] == +1) dq[i].push_back(j);
}
for(int j=0; j<sz(B[i]); j++){
if(B[i][j] == 0) B[i][j] = -1;
else B[i][j] = 0;
}
}
for(int i = 0; i < k; i++){
vector<int> idx(sz(B));
iota(all(idx), 0);
sort(all(idx), [&](const int &a, const int &b){
return bcnt[a] < bcnt[b];
});
for(int j=0; j<sz(B); j++){
int x = idx[j];
int y = (j < sz(B) / 2 ? dq[x].front() : dq[x].back());
B[x][y] = i;
if(j < sz(B) / 2) dq[x].pop_front();
else{
dq[x].pop_back();
bcnt[x]--;
}
}
}
allocate_tickets(B);
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = sz(x);
int m = sz(x[0]);
vector<vector<int>> B(n);
vector<node> v;
for(auto &i : B) i.resize(m);
lint sum = 0;
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
sum -= x[i][j];
B[i][j] = -1;
v.push_back({i, j, x[i][m-1-j]+x[i][k-1-j]});
}
}
sort(all(v));
reverse(all(v));
for(int i=0; i<sz(v)/2; i++){
sum += v[i].v;
B[v[i].x][k - 1 - v[i].y] = 0;
B[v[i].x][m - 1 - v[i].y] = +1;
}
BACKTRACK(B, k);
return sum;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
2 ms |
1300 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
4 |
Correct |
2 ms |
1280 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
4 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
1 ms |
1280 KB |
Output is correct |
3 |
Correct |
1 ms |
1384 KB |
Output is correct |
4 |
Correct |
4 ms |
1536 KB |
Output is correct |
5 |
Correct |
33 ms |
3840 KB |
Output is correct |
6 |
Correct |
844 ms |
61360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
1 ms |
1312 KB |
Output is correct |
3 |
Correct |
1 ms |
1280 KB |
Output is correct |
4 |
Correct |
3 ms |
1536 KB |
Output is correct |
5 |
Correct |
29 ms |
4064 KB |
Output is correct |
6 |
Correct |
719 ms |
70968 KB |
Output is correct |
7 |
Correct |
808 ms |
76948 KB |
Output is correct |
8 |
Correct |
6 ms |
1728 KB |
Output is correct |
9 |
Correct |
1 ms |
1280 KB |
Output is correct |
10 |
Correct |
1 ms |
1280 KB |
Output is correct |
11 |
Correct |
1 ms |
1280 KB |
Output is correct |
12 |
Correct |
9 ms |
2112 KB |
Output is correct |
13 |
Correct |
26 ms |
3832 KB |
Output is correct |
14 |
Correct |
28 ms |
4088 KB |
Output is correct |
15 |
Correct |
839 ms |
82604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1280 KB |
Output is correct |
2 |
Correct |
1 ms |
1408 KB |
Output is correct |
3 |
Correct |
1 ms |
1280 KB |
Output is correct |
4 |
Correct |
5 ms |
1536 KB |
Output is correct |
5 |
Correct |
46 ms |
4852 KB |
Output is correct |
6 |
Correct |
8 ms |
1860 KB |
Output is correct |
7 |
Correct |
10 ms |
2144 KB |
Output is correct |
8 |
Correct |
1246 ms |
88848 KB |
Output is correct |
9 |
Correct |
1192 ms |
82780 KB |
Output is correct |
10 |
Correct |
1192 ms |
83064 KB |
Output is correct |
11 |
Correct |
1263 ms |
88860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
4 ms |
1536 KB |
Output is correct |
3 |
Correct |
4 ms |
1536 KB |
Output is correct |
4 |
Correct |
4 ms |
1536 KB |
Output is correct |
5 |
Correct |
4 ms |
1664 KB |
Output is correct |
6 |
Correct |
5 ms |
1536 KB |
Output is correct |
7 |
Correct |
2 ms |
1440 KB |
Output is correct |
8 |
Correct |
2 ms |
1408 KB |
Output is correct |
9 |
Correct |
4 ms |
1536 KB |
Output is correct |
10 |
Correct |
4 ms |
1536 KB |
Output is correct |
11 |
Correct |
4 ms |
1536 KB |
Output is correct |
12 |
Correct |
4 ms |
1568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
4 ms |
1536 KB |
Output is correct |
3 |
Correct |
4 ms |
1536 KB |
Output is correct |
4 |
Correct |
4 ms |
1536 KB |
Output is correct |
5 |
Correct |
4 ms |
1664 KB |
Output is correct |
6 |
Correct |
5 ms |
1536 KB |
Output is correct |
7 |
Correct |
2 ms |
1440 KB |
Output is correct |
8 |
Correct |
2 ms |
1408 KB |
Output is correct |
9 |
Correct |
4 ms |
1536 KB |
Output is correct |
10 |
Correct |
4 ms |
1536 KB |
Output is correct |
11 |
Correct |
4 ms |
1536 KB |
Output is correct |
12 |
Correct |
4 ms |
1568 KB |
Output is correct |
13 |
Correct |
32 ms |
3832 KB |
Output is correct |
14 |
Correct |
33 ms |
3960 KB |
Output is correct |
15 |
Correct |
51 ms |
4080 KB |
Output is correct |
16 |
Correct |
56 ms |
4844 KB |
Output is correct |
17 |
Correct |
2 ms |
1408 KB |
Output is correct |
18 |
Correct |
4 ms |
1568 KB |
Output is correct |
19 |
Correct |
2 ms |
1408 KB |
Output is correct |
20 |
Correct |
34 ms |
4216 KB |
Output is correct |
21 |
Correct |
40 ms |
4216 KB |
Output is correct |
22 |
Correct |
42 ms |
4468 KB |
Output is correct |
23 |
Correct |
44 ms |
4472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
2 ms |
1300 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
4 |
Correct |
2 ms |
1280 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
4 ms |
1792 KB |
Output is correct |
7 |
Correct |
1 ms |
1280 KB |
Output is correct |
8 |
Correct |
1 ms |
1280 KB |
Output is correct |
9 |
Correct |
1 ms |
1384 KB |
Output is correct |
10 |
Correct |
4 ms |
1536 KB |
Output is correct |
11 |
Correct |
33 ms |
3840 KB |
Output is correct |
12 |
Correct |
844 ms |
61360 KB |
Output is correct |
13 |
Correct |
1 ms |
1280 KB |
Output is correct |
14 |
Correct |
1 ms |
1312 KB |
Output is correct |
15 |
Correct |
1 ms |
1280 KB |
Output is correct |
16 |
Correct |
3 ms |
1536 KB |
Output is correct |
17 |
Correct |
29 ms |
4064 KB |
Output is correct |
18 |
Correct |
719 ms |
70968 KB |
Output is correct |
19 |
Correct |
808 ms |
76948 KB |
Output is correct |
20 |
Correct |
6 ms |
1728 KB |
Output is correct |
21 |
Correct |
1 ms |
1280 KB |
Output is correct |
22 |
Correct |
1 ms |
1280 KB |
Output is correct |
23 |
Correct |
1 ms |
1280 KB |
Output is correct |
24 |
Correct |
9 ms |
2112 KB |
Output is correct |
25 |
Correct |
26 ms |
3832 KB |
Output is correct |
26 |
Correct |
28 ms |
4088 KB |
Output is correct |
27 |
Correct |
839 ms |
82604 KB |
Output is correct |
28 |
Correct |
2 ms |
1280 KB |
Output is correct |
29 |
Correct |
1 ms |
1408 KB |
Output is correct |
30 |
Correct |
1 ms |
1280 KB |
Output is correct |
31 |
Correct |
5 ms |
1536 KB |
Output is correct |
32 |
Correct |
46 ms |
4852 KB |
Output is correct |
33 |
Correct |
8 ms |
1860 KB |
Output is correct |
34 |
Correct |
10 ms |
2144 KB |
Output is correct |
35 |
Correct |
1246 ms |
88848 KB |
Output is correct |
36 |
Correct |
1192 ms |
82780 KB |
Output is correct |
37 |
Correct |
1192 ms |
83064 KB |
Output is correct |
38 |
Correct |
1263 ms |
88860 KB |
Output is correct |
39 |
Correct |
1 ms |
1280 KB |
Output is correct |
40 |
Correct |
4 ms |
1536 KB |
Output is correct |
41 |
Correct |
4 ms |
1536 KB |
Output is correct |
42 |
Correct |
4 ms |
1536 KB |
Output is correct |
43 |
Correct |
4 ms |
1664 KB |
Output is correct |
44 |
Correct |
5 ms |
1536 KB |
Output is correct |
45 |
Correct |
2 ms |
1440 KB |
Output is correct |
46 |
Correct |
2 ms |
1408 KB |
Output is correct |
47 |
Correct |
4 ms |
1536 KB |
Output is correct |
48 |
Correct |
4 ms |
1536 KB |
Output is correct |
49 |
Correct |
4 ms |
1536 KB |
Output is correct |
50 |
Correct |
4 ms |
1568 KB |
Output is correct |
51 |
Correct |
32 ms |
3832 KB |
Output is correct |
52 |
Correct |
33 ms |
3960 KB |
Output is correct |
53 |
Correct |
51 ms |
4080 KB |
Output is correct |
54 |
Correct |
56 ms |
4844 KB |
Output is correct |
55 |
Correct |
2 ms |
1408 KB |
Output is correct |
56 |
Correct |
4 ms |
1568 KB |
Output is correct |
57 |
Correct |
2 ms |
1408 KB |
Output is correct |
58 |
Correct |
34 ms |
4216 KB |
Output is correct |
59 |
Correct |
40 ms |
4216 KB |
Output is correct |
60 |
Correct |
42 ms |
4468 KB |
Output is correct |
61 |
Correct |
44 ms |
4472 KB |
Output is correct |
62 |
Correct |
93 ms |
8056 KB |
Output is correct |
63 |
Correct |
93 ms |
8184 KB |
Output is correct |
64 |
Correct |
126 ms |
10976 KB |
Output is correct |
65 |
Correct |
460 ms |
32600 KB |
Output is correct |
66 |
Correct |
538 ms |
40008 KB |
Output is correct |
67 |
Correct |
9 ms |
2112 KB |
Output is correct |
68 |
Correct |
10 ms |
1988 KB |
Output is correct |
69 |
Correct |
784 ms |
61312 KB |
Output is correct |
70 |
Correct |
1000 ms |
70960 KB |
Output is correct |
71 |
Correct |
1245 ms |
88960 KB |
Output is correct |
72 |
Correct |
1033 ms |
84472 KB |
Output is correct |
73 |
Correct |
1154 ms |
83632 KB |
Output is correct |
74 |
Correct |
828 ms |
70936 KB |
Output is correct |
75 |
Correct |
998 ms |
70548 KB |
Output is correct |