#include "tickets.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define int long long
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 1505;
int n, m, K, ans, lol[nmax][nmax], ultim[nmax];
vector<int>slava[nmax], marian[nmax];
vector<vector<int32_t>>haida;
void simuleaza(){
haida.resize(n, vector<int32_t>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(lol[i][j] == 0){
haida[i][j] = -1;
}
else if(lol[i][j] == 2){
slava[i].push_back(j);
}
else{
marian[i].push_back(j);
}
}
}
set<pair<int,int>>alic;
for(int i=0;i<K;i++){
alic.clear();
for(int j=0;j<n;j++){
alic.insert({slava[j].size(), j});
}
for(int j=0;j<n;j++) ultim[j] = 0;
auto it = alic.end();
for(int j=1;j<=n/2;j++){
--it;
haida[it->sc][slava[it->sc].back()] = i;
slava[it->sc].pop_back();
ultim[it->sc] = 1;
}
for(int j=0;j<n;j++){
if(ultim[j] != 1){
haida[j][marian[j].back()] = i;
marian[j].pop_back();
}
}
}
}
int find_maximum(int32_t k, vector<vector<int32_t>> x) {
n = x.size();
m = x[0].size();
K = k;
vector<pair<int,pair<int,int>>>xd;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
ans -= (long long)x[i][j];
lol[i][j] = 1;
xd.push_back({x[i][j] + x[i][m-(k-j)], {i, j}});
}
}
sort(all(xd));
reverse(all(xd));
for(int i=0;i<(k*n/2);i++){
auto it = xd[i];
lol[it.sc.fr][it.sc.sc] = 0;
lol[it.sc.fr][m-(k-it.sc.sc)] = 2;
ans += it.fr;
}
simuleaza();
allocate_tickets(haida);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
1620 KB |
Output is correct |
6 |
Correct |
4 ms |
6868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
852 KB |
Output is correct |
5 |
Correct |
22 ms |
3964 KB |
Output is correct |
6 |
Correct |
497 ms |
57624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
980 KB |
Output is correct |
5 |
Correct |
30 ms |
5684 KB |
Output is correct |
6 |
Correct |
716 ms |
99556 KB |
Output is correct |
7 |
Correct |
790 ms |
115668 KB |
Output is correct |
8 |
Correct |
4 ms |
1360 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
8 ms |
2132 KB |
Output is correct |
13 |
Correct |
25 ms |
6232 KB |
Output is correct |
14 |
Correct |
25 ms |
5188 KB |
Output is correct |
15 |
Correct |
842 ms |
123340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
4 ms |
1044 KB |
Output is correct |
5 |
Correct |
39 ms |
7380 KB |
Output is correct |
6 |
Correct |
6 ms |
1232 KB |
Output is correct |
7 |
Correct |
11 ms |
7504 KB |
Output is correct |
8 |
Correct |
1132 ms |
139216 KB |
Output is correct |
9 |
Correct |
1128 ms |
133196 KB |
Output is correct |
10 |
Correct |
1178 ms |
131980 KB |
Output is correct |
11 |
Correct |
1201 ms |
139132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
3 ms |
980 KB |
Output is correct |
5 |
Correct |
3 ms |
980 KB |
Output is correct |
6 |
Correct |
3 ms |
1048 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
3 ms |
980 KB |
Output is correct |
11 |
Correct |
3 ms |
1048 KB |
Output is correct |
12 |
Correct |
3 ms |
1048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
852 KB |
Output is correct |
4 |
Correct |
3 ms |
980 KB |
Output is correct |
5 |
Correct |
3 ms |
980 KB |
Output is correct |
6 |
Correct |
3 ms |
1048 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
3 ms |
980 KB |
Output is correct |
11 |
Correct |
3 ms |
1048 KB |
Output is correct |
12 |
Correct |
3 ms |
1048 KB |
Output is correct |
13 |
Correct |
22 ms |
4156 KB |
Output is correct |
14 |
Correct |
22 ms |
4476 KB |
Output is correct |
15 |
Correct |
29 ms |
5780 KB |
Output is correct |
16 |
Correct |
41 ms |
7464 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
3 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1748 KB |
Output is correct |
20 |
Correct |
31 ms |
5960 KB |
Output is correct |
21 |
Correct |
32 ms |
5856 KB |
Output is correct |
22 |
Correct |
37 ms |
6972 KB |
Output is correct |
23 |
Correct |
37 ms |
6864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
1620 KB |
Output is correct |
6 |
Correct |
4 ms |
6868 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
852 KB |
Output is correct |
11 |
Correct |
22 ms |
3964 KB |
Output is correct |
12 |
Correct |
497 ms |
57624 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
980 KB |
Output is correct |
17 |
Correct |
30 ms |
5684 KB |
Output is correct |
18 |
Correct |
716 ms |
99556 KB |
Output is correct |
19 |
Correct |
790 ms |
115668 KB |
Output is correct |
20 |
Correct |
4 ms |
1360 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
8 ms |
2132 KB |
Output is correct |
25 |
Correct |
25 ms |
6232 KB |
Output is correct |
26 |
Correct |
25 ms |
5188 KB |
Output is correct |
27 |
Correct |
842 ms |
123340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
4 ms |
1044 KB |
Output is correct |
32 |
Correct |
39 ms |
7380 KB |
Output is correct |
33 |
Correct |
6 ms |
1232 KB |
Output is correct |
34 |
Correct |
11 ms |
7504 KB |
Output is correct |
35 |
Correct |
1132 ms |
139216 KB |
Output is correct |
36 |
Correct |
1128 ms |
133196 KB |
Output is correct |
37 |
Correct |
1178 ms |
131980 KB |
Output is correct |
38 |
Correct |
1201 ms |
139132 KB |
Output is correct |
39 |
Correct |
0 ms |
340 KB |
Output is correct |
40 |
Correct |
2 ms |
852 KB |
Output is correct |
41 |
Correct |
2 ms |
852 KB |
Output is correct |
42 |
Correct |
3 ms |
980 KB |
Output is correct |
43 |
Correct |
3 ms |
980 KB |
Output is correct |
44 |
Correct |
3 ms |
1048 KB |
Output is correct |
45 |
Correct |
1 ms |
468 KB |
Output is correct |
46 |
Correct |
1 ms |
724 KB |
Output is correct |
47 |
Correct |
3 ms |
980 KB |
Output is correct |
48 |
Correct |
3 ms |
980 KB |
Output is correct |
49 |
Correct |
3 ms |
1048 KB |
Output is correct |
50 |
Correct |
3 ms |
1048 KB |
Output is correct |
51 |
Correct |
22 ms |
4156 KB |
Output is correct |
52 |
Correct |
22 ms |
4476 KB |
Output is correct |
53 |
Correct |
29 ms |
5780 KB |
Output is correct |
54 |
Correct |
41 ms |
7464 KB |
Output is correct |
55 |
Correct |
1 ms |
468 KB |
Output is correct |
56 |
Correct |
3 ms |
1876 KB |
Output is correct |
57 |
Correct |
2 ms |
1748 KB |
Output is correct |
58 |
Correct |
31 ms |
5960 KB |
Output is correct |
59 |
Correct |
32 ms |
5856 KB |
Output is correct |
60 |
Correct |
37 ms |
6972 KB |
Output is correct |
61 |
Correct |
37 ms |
6864 KB |
Output is correct |
62 |
Correct |
58 ms |
9644 KB |
Output is correct |
63 |
Correct |
58 ms |
10028 KB |
Output is correct |
64 |
Correct |
113 ms |
17836 KB |
Output is correct |
65 |
Correct |
333 ms |
48796 KB |
Output is correct |
66 |
Correct |
451 ms |
65008 KB |
Output is correct |
67 |
Correct |
10 ms |
7504 KB |
Output is correct |
68 |
Correct |
6 ms |
1232 KB |
Output is correct |
69 |
Correct |
510 ms |
57948 KB |
Output is correct |
70 |
Correct |
775 ms |
100884 KB |
Output is correct |
71 |
Correct |
1052 ms |
139436 KB |
Output is correct |
72 |
Correct |
1048 ms |
133800 KB |
Output is correct |
73 |
Correct |
1016 ms |
130892 KB |
Output is correct |
74 |
Correct |
806 ms |
100868 KB |
Output is correct |
75 |
Correct |
801 ms |
99148 KB |
Output is correct |