#include "tickets.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
ll res=0;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
res-=x[i][j];
}
}
vector<int> klkp(n,0);
priority_queue<pair<int,int> > pq;
for(int i=0;i<n;i++) pq.push({x[i][m-1]+x[i][k-1],i});
for(int i=0;i<n*k/2;i++){
//for(int j=0;j<n;j++){
// if(klkp[j]==k) continue;
// maxi=max(maxi,{x[j][m-1-klkp[j]]+x[j][k-1-klkp[j]],j});
//}
pair<int,int> maxi=pq.top();
pq.pop();
res+=maxi.first;
klkp[maxi.second]++;
//
if(klkp[maxi.second]==k) continue;
pq.push({x[maxi.second][m-1-klkp[maxi.second]]+x[maxi.second][k-1-klkp[maxi.second]],maxi.second});
}
vector<int> uzeop(n,0);
bool uspeo=true;
for(int i=0;i<k;i++){
vector<pair<int,int> > sta(n,{0,0});
for(int j=0;j<n;j++){
sta[j]={-klkp[j]+uzeop[j],j};
}
vector<bool> uzimamp(n,false);
sort(sta.begin(),sta.end());
for(int i=0;i<n/2;i++){
uzimamp[sta[i].second]=true;
}
for(int j=0;j<n;j++){
if(uzimamp[j]){
answer[j][m-1-uzeop[j]]=i;
uzeop[j]++;
}else{
answer[j][i-uzeop[j]]=i;
}
}
}
for(int i=0;i<n;i++) if(uzeop[i]!=klkp[i]) uspeo=false;
if(!uspeo) exit(-1);
allocate_tickets(answer);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
2508 KB |
Output is correct |
6 |
Correct |
393 ms |
51624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
2440 KB |
Output is correct |
6 |
Correct |
397 ms |
52628 KB |
Output is correct |
7 |
Correct |
416 ms |
57128 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
4 ms |
852 KB |
Output is correct |
13 |
Correct |
14 ms |
2120 KB |
Output is correct |
14 |
Correct |
14 ms |
2180 KB |
Output is correct |
15 |
Correct |
432 ms |
57748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
20 ms |
2528 KB |
Output is correct |
6 |
Correct |
3 ms |
800 KB |
Output is correct |
7 |
Correct |
5 ms |
956 KB |
Output is correct |
8 |
Correct |
533 ms |
54240 KB |
Output is correct |
9 |
Correct |
521 ms |
70992 KB |
Output is correct |
10 |
Correct |
534 ms |
71040 KB |
Output is correct |
11 |
Correct |
561 ms |
76052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
308 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
308 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
16 ms |
2516 KB |
Output is correct |
14 |
Correct |
16 ms |
2516 KB |
Output is correct |
15 |
Correct |
18 ms |
2572 KB |
Output is correct |
16 |
Correct |
21 ms |
2604 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
18 ms |
2436 KB |
Output is correct |
21 |
Correct |
20 ms |
2420 KB |
Output is correct |
22 |
Correct |
20 ms |
2404 KB |
Output is correct |
23 |
Correct |
22 ms |
2540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
16 ms |
2508 KB |
Output is correct |
12 |
Correct |
393 ms |
51624 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
16 ms |
2440 KB |
Output is correct |
18 |
Correct |
397 ms |
52628 KB |
Output is correct |
19 |
Correct |
416 ms |
57128 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
300 KB |
Output is correct |
24 |
Correct |
4 ms |
852 KB |
Output is correct |
25 |
Correct |
14 ms |
2120 KB |
Output is correct |
26 |
Correct |
14 ms |
2180 KB |
Output is correct |
27 |
Correct |
432 ms |
57748 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
20 ms |
2528 KB |
Output is correct |
33 |
Correct |
3 ms |
800 KB |
Output is correct |
34 |
Correct |
5 ms |
956 KB |
Output is correct |
35 |
Correct |
533 ms |
54240 KB |
Output is correct |
36 |
Correct |
521 ms |
70992 KB |
Output is correct |
37 |
Correct |
534 ms |
71040 KB |
Output is correct |
38 |
Correct |
561 ms |
76052 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
2 ms |
468 KB |
Output is correct |
41 |
Correct |
2 ms |
468 KB |
Output is correct |
42 |
Correct |
2 ms |
468 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
2 ms |
468 KB |
Output is correct |
45 |
Correct |
1 ms |
300 KB |
Output is correct |
46 |
Correct |
1 ms |
308 KB |
Output is correct |
47 |
Correct |
2 ms |
468 KB |
Output is correct |
48 |
Correct |
2 ms |
468 KB |
Output is correct |
49 |
Correct |
2 ms |
468 KB |
Output is correct |
50 |
Correct |
2 ms |
468 KB |
Output is correct |
51 |
Correct |
16 ms |
2516 KB |
Output is correct |
52 |
Correct |
16 ms |
2516 KB |
Output is correct |
53 |
Correct |
18 ms |
2572 KB |
Output is correct |
54 |
Correct |
21 ms |
2604 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
2 ms |
468 KB |
Output is correct |
57 |
Correct |
1 ms |
340 KB |
Output is correct |
58 |
Correct |
18 ms |
2436 KB |
Output is correct |
59 |
Correct |
20 ms |
2420 KB |
Output is correct |
60 |
Correct |
20 ms |
2404 KB |
Output is correct |
61 |
Correct |
22 ms |
2540 KB |
Output is correct |
62 |
Correct |
42 ms |
8420 KB |
Output is correct |
63 |
Correct |
43 ms |
8436 KB |
Output is correct |
64 |
Correct |
56 ms |
8544 KB |
Output is correct |
65 |
Correct |
197 ms |
33056 KB |
Output is correct |
66 |
Correct |
231 ms |
33600 KB |
Output is correct |
67 |
Correct |
5 ms |
980 KB |
Output is correct |
68 |
Correct |
4 ms |
700 KB |
Output is correct |
69 |
Correct |
383 ms |
73104 KB |
Output is correct |
70 |
Correct |
463 ms |
74132 KB |
Output is correct |
71 |
Correct |
532 ms |
75948 KB |
Output is correct |
72 |
Correct |
483 ms |
60492 KB |
Output is correct |
73 |
Correct |
535 ms |
73216 KB |
Output is correct |
74 |
Correct |
418 ms |
59108 KB |
Output is correct |
75 |
Correct |
462 ms |
71832 KB |
Output is correct |