#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef pair <int,int> ii;
long long find_maximum(int k, std::vector<std::vector<int>> x)
{
int n = x.size();
int m = x[0].size();
vector <priority_queue <ii> > smalls(n);
vector <priority_queue <ii> > bigs(n);
for(int i=0;i<n;i++)
{
sort(x[i].begin(),x[i].end());
for(int j=0;j<m-k;j++)
{
smalls[i].push(ii(-x[i][j],j));
}
for(int j=m-k;j<m;j++)
{
bigs[i].push(ii(-x[i][j],j));
}
}
priority_queue <ii> pq;
for(int i=0;i<n;i++)
{
int best=bigs[i].top().first*2;
if(smalls[i].size())
{
best=max(best,bigs[i].top().first+smalls[i].top().first);
}
pq.push(ii(best,i));
}
vector <vector <ii> > small_values(n);
vector <vector <ii> > big_values(n);
for(int i=0;i<n*k/2;i++)
{
int loc=pq.top().second;
pq.pop();
int val=bigs[loc].top().first;
int loc2=bigs[loc].top().second;
bigs[loc].pop();
smalls[loc].push(ii(val,loc2));
small_values[loc].pb(smalls[loc].top());
smalls[loc].pop();
if(bigs[loc].size())
{
int best=bigs[loc].top().first*2;
if(smalls[loc].size())
{
best=max(best,bigs[loc].top().first+smalls[loc].top().first);
}
pq.push(ii(best,loc));
}
}
for(int i=0;i<n;i++)
{
while(bigs[i].size())
{
big_values[i].pb(bigs[i].top());
bigs[i].pop();
}
}
/*for(int i=0;i<n;i++)
{
for(int j=0;j<small_values[i].size();j++)
{
printf("%d %d ",small_values[i][j].first,small_values[i][j].second);
}
printf(" ");
for(int j=0;j<big_values[i].size();j++)
{
printf("%d %d ",big_values[i][j].first,big_values[i][j].second);
}
printf("\n");
}*/
vector <vector <int> > answer(n,vector <int> (m,-1));
long long ans=0;
for(int i=0;i<k;i++)
{
int small=n/2;
int big=n/2;
vector <bool> t(n,0);
for(int j=0;j<n;j++)
{
if(small_values[j].size()==0)
{
t[j]=1;
big--;
ans-=big_values[j].back().first;
answer[j][big_values[j].back().second]=i;
big_values[j].pop_back();
}
else if(big_values[j].size()==0)
{
t[j]=1;
small--;
ans+=small_values[j].back().first;
answer[j][small_values[j].back().second]=i;
small_values[j].pop_back();
}
}
for(int j=0;j<n;j++)
{
if(t[j]==0)
{
if(big>0)
{
t[j]=1;
big--;
ans-=big_values[j].back().first;
answer[j][big_values[j].back().second]=i;
big_values[j].pop_back();
}
else
{
t[j]=1;
small--;
ans+=small_values[j].back().first;
answer[j][small_values[j].back().second]=i;
small_values[j].pop_back();
}
}
}
}
allocate_tickets(answer);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
260 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
568 KB |
Output is correct |
5 |
Correct |
23 ms |
4400 KB |
Output is correct |
6 |
Correct |
527 ms |
96948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
240 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
568 KB |
Output is correct |
5 |
Correct |
32 ms |
4316 KB |
Output is correct |
6 |
Correct |
680 ms |
93140 KB |
Output is correct |
7 |
Correct |
707 ms |
91480 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
10 ms |
1208 KB |
Output is correct |
13 |
Correct |
24 ms |
3504 KB |
Output is correct |
14 |
Correct |
22 ms |
3728 KB |
Output is correct |
15 |
Correct |
736 ms |
106780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
38 ms |
4940 KB |
Output is correct |
6 |
Correct |
6 ms |
980 KB |
Output is correct |
7 |
Correct |
8 ms |
1492 KB |
Output is correct |
8 |
Correct |
1065 ms |
103044 KB |
Output is correct |
9 |
Correct |
882 ms |
97856 KB |
Output is correct |
10 |
Correct |
914 ms |
96056 KB |
Output is correct |
11 |
Correct |
961 ms |
103108 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 |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
564 KB |
Output is correct |
5 |
Correct |
3 ms |
568 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
592 KB |
Output is correct |
10 |
Correct |
2 ms |
624 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
4 ms |
596 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 |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
564 KB |
Output is correct |
5 |
Correct |
3 ms |
568 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
592 KB |
Output is correct |
10 |
Correct |
2 ms |
624 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
4 ms |
596 KB |
Output is correct |
13 |
Correct |
26 ms |
4428 KB |
Output is correct |
14 |
Correct |
26 ms |
4552 KB |
Output is correct |
15 |
Correct |
26 ms |
5068 KB |
Output is correct |
16 |
Correct |
31 ms |
5824 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
28 ms |
4280 KB |
Output is correct |
21 |
Correct |
29 ms |
4724 KB |
Output is correct |
22 |
Correct |
34 ms |
4984 KB |
Output is correct |
23 |
Correct |
30 ms |
5464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
260 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
3 ms |
568 KB |
Output is correct |
11 |
Correct |
23 ms |
4400 KB |
Output is correct |
12 |
Correct |
527 ms |
96948 KB |
Output is correct |
13 |
Correct |
1 ms |
240 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
300 KB |
Output is correct |
16 |
Correct |
2 ms |
568 KB |
Output is correct |
17 |
Correct |
32 ms |
4316 KB |
Output is correct |
18 |
Correct |
680 ms |
93140 KB |
Output is correct |
19 |
Correct |
707 ms |
91480 KB |
Output is correct |
20 |
Correct |
3 ms |
724 KB |
Output is correct |
21 |
Correct |
1 ms |
300 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
10 ms |
1208 KB |
Output is correct |
25 |
Correct |
24 ms |
3504 KB |
Output is correct |
26 |
Correct |
22 ms |
3728 KB |
Output is correct |
27 |
Correct |
736 ms |
106780 KB |
Output is correct |
28 |
Correct |
0 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 |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
38 ms |
4940 KB |
Output is correct |
33 |
Correct |
6 ms |
980 KB |
Output is correct |
34 |
Correct |
8 ms |
1492 KB |
Output is correct |
35 |
Correct |
1065 ms |
103044 KB |
Output is correct |
36 |
Correct |
882 ms |
97856 KB |
Output is correct |
37 |
Correct |
914 ms |
96056 KB |
Output is correct |
38 |
Correct |
961 ms |
103108 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 |
492 KB |
Output is correct |
42 |
Correct |
2 ms |
564 KB |
Output is correct |
43 |
Correct |
3 ms |
568 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
2 ms |
592 KB |
Output is correct |
48 |
Correct |
2 ms |
624 KB |
Output is correct |
49 |
Correct |
4 ms |
596 KB |
Output is correct |
50 |
Correct |
4 ms |
596 KB |
Output is correct |
51 |
Correct |
26 ms |
4428 KB |
Output is correct |
52 |
Correct |
26 ms |
4552 KB |
Output is correct |
53 |
Correct |
26 ms |
5068 KB |
Output is correct |
54 |
Correct |
31 ms |
5824 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
2 ms |
596 KB |
Output is correct |
57 |
Correct |
1 ms |
468 KB |
Output is correct |
58 |
Correct |
28 ms |
4280 KB |
Output is correct |
59 |
Correct |
29 ms |
4724 KB |
Output is correct |
60 |
Correct |
34 ms |
4984 KB |
Output is correct |
61 |
Correct |
30 ms |
5464 KB |
Output is correct |
62 |
Correct |
59 ms |
10452 KB |
Output is correct |
63 |
Correct |
58 ms |
10604 KB |
Output is correct |
64 |
Correct |
116 ms |
13404 KB |
Output is correct |
65 |
Correct |
326 ms |
46524 KB |
Output is correct |
66 |
Correct |
443 ms |
51772 KB |
Output is correct |
67 |
Correct |
7 ms |
1620 KB |
Output is correct |
68 |
Correct |
6 ms |
1108 KB |
Output is correct |
69 |
Correct |
544 ms |
97264 KB |
Output is correct |
70 |
Correct |
933 ms |
110980 KB |
Output is correct |
71 |
Correct |
1016 ms |
124844 KB |
Output is correct |
72 |
Correct |
1006 ms |
108208 KB |
Output is correct |
73 |
Correct |
971 ms |
120484 KB |
Output is correct |
74 |
Correct |
801 ms |
96096 KB |
Output is correct |
75 |
Correct |
800 ms |
107720 KB |
Output is correct |