#include "tickets.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
typedef long long ll;
#define INF 100000000000007
typedef pair<int,int>pairll;
#define fr first
#define sc second
#define pb push_back
map<ll,ll>mp[1507];
vector<vector<int> >ans;
vector<vector<int> >v;
priority_queue<pairll>ql,qr,q;
ll res,l[1507],r[1507],n,m;
ll L(ll x){
if(l[x]==0)return -INF;
return v[x][r[x]]+v[x][l[x]-1];
}
ll R(ll x){
if(r[x]==m-1)return -INF;
return -v[x][l[x]]-v[x][r[x]+1];
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
n = x.size();
m = x[0].size();
if(k==m){
ll res=0;
for(int i=1;i<=n;i++){
vector<int>ro;
for(int j=0;j<m;j++){
res+=x[i-1][j];
ro.push_back(-1);
}
ans.push_back(ro);
q.push({-x[i-1][0],i});
}
//exit(1);
//cout<<q.size()<<endl;
for(int i=1;i<=(n*m)/2;i++){
//cout<<q.size()<<endl;
if(q.size()>0){
ll m1=q.top().fr;
ll m2=q.top().sc;
//cout<<m1<<" "<<m2<<" " <<rs[m2]<<endl;
l[m2]++;
q.pop();
res+=m1*2;
if(l[m2]<m)q.push({-x[m2-1][l[m2]],m2});
}
}
//cout<<q.size()<<endl;
//cout<<1<<endl;
ll g=0;
for(int i=n;i>=1;i--){
//cout<<i<<" "<<rs[i]<<endl;
ll h=g;
//cout<<i<<" "<<rs[i]<<endl;
for(int j=0;j<l[i];j++){
//cout<<j<<" "<<h<<endl;
ans[i-1][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
// cout<<endl;
g=h;
for(int j=m-1;j>=m-(k-l[i]);j--){
ans[i-1][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
//cout<<endl;
}
allocate_tickets(ans);
return res;
}
swap(v,x);
for(int i=0;i<n;i++){
vector<int>rs;
rs.clear();
for(int i=0;i<m;i++){
rs.pb(-1);
}
ans.pb(rs);
l[i]=(k+(i%2))/2;
r[i]=m-(k+(i+1)%2)/2-1;
for(int j=0;j<l[i];j++){
res-=v[i][j];
}
for(int j=r[i]+1;j<m;j++){
res+=v[i][j];
}
ql.push({L(i),i});
qr.push({R(i),i});
//cout<<i<<" "<<l[i]<<" "<<r[i]<<endl;
}
while(1){
while(ql.top().fr!=L(ql.top().sc))ql.pop();
while(qr.top().fr!=R(qr.top().sc))qr.pop();
ll m1=ql.top().sc;
ll m2=qr.top().sc;
if(L(m1)+R(m2)<=0)break;
ql.pop();
qr.pop();
if(m1==m2){
while(ql.top().fr!=L(ql.top().sc))ql.pop();
while(qr.top().fr!=R(qr.top().sc))qr.pop();
if(ql.size()==0 || qr.size()==0)break;
ll m3=ql.top().sc;
ll m4=qr.top().sc;
ql.pop();
qr.pop();
if(L(m3)+R(m2)<=0 && L(m1)+R(m4)<=0)break;
if(L(m3)+R(m2)>L(m1)+R(m4)){
res+=L(m3)+R(m2);
l[m3]--;
r[m3]--;
l[m2]++;
r[m2]++;
ql.push({L(m3),m3});
qr.push({R(m2),m2});
ql.push({L(m2),m2});
qr.push({R(m3),m3});
//ql.push({L(m1),m1});
qr.push({R(m4),m4});
}else{
res+=L(m1)+R(m4);
l[m1]--;
r[m1]--;
l[m4]++;
r[m4]++;
ql.push({L(m1),m1});
qr.push({R(m4),m4});
ql.push({L(m4),m4});
qr.push({R(m1),m1});
//ql.push({L(m1),m1});
ql.push({L(m3),m3});
}
}else{
res+=L(m1);
res+=R(m2);
l[m1]--;
r[m1]--;
l[m2]++;
r[m2]++;
ql.push({L(m1),m1});
qr.push({R(m2),m2});
ql.push({L(m2),m2});
qr.push({R(m1),m1});
}
}
ll g=0;
for(int i=n-1;i>=0;i--){
//cout<<i<<" "<<rs[i]<<endl;
ll h=g;
//cout<<i<<" "<<rs[i]<<endl;
for(int j=0;j<l[i];j++){
//cout<<j<<" "<<h<<endl;
ans[i][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
// cout<<endl;
g=h;
for(int j=m-1;j>=m-(k-l[i]);j--){
ans[i][j]=(h%k);
h++;
//cout<<j<<" "<<h<<endl;
//cout<<j<<" ";
}
//cout<<endl;
}
allocate_tickets(ans);
return res;
}
# |
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 |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
380 KB |
Output is correct |
3 |
Correct |
1 ms |
372 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
28 ms |
3300 KB |
Output is correct |
6 |
Correct |
439 ms |
53432 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 |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
16 ms |
2644 KB |
Output is correct |
6 |
Correct |
385 ms |
56836 KB |
Output is correct |
7 |
Correct |
397 ms |
57252 KB |
Output is correct |
8 |
Correct |
3 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
5 ms |
980 KB |
Output is correct |
13 |
Correct |
16 ms |
2316 KB |
Output is correct |
14 |
Correct |
15 ms |
2260 KB |
Output is correct |
15 |
Correct |
437 ms |
60252 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 |
468 KB |
Output is correct |
5 |
Correct |
23 ms |
2536 KB |
Output is correct |
6 |
Correct |
4 ms |
724 KB |
Output is correct |
7 |
Correct |
5 ms |
852 KB |
Output is correct |
8 |
Correct |
576 ms |
54260 KB |
Output is correct |
9 |
Correct |
529 ms |
50624 KB |
Output is correct |
10 |
Correct |
526 ms |
50736 KB |
Output is correct |
11 |
Correct |
589 ms |
54404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 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 |
536 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 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 |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 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 |
536 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 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 |
596 KB |
Output is correct |
13 |
Correct |
19 ms |
3352 KB |
Output is correct |
14 |
Correct |
20 ms |
3324 KB |
Output is correct |
15 |
Correct |
21 ms |
3276 KB |
Output is correct |
16 |
Correct |
23 ms |
3372 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 |
520 KB |
Output is correct |
20 |
Correct |
19 ms |
2808 KB |
Output is correct |
21 |
Correct |
20 ms |
3340 KB |
Output is correct |
22 |
Correct |
19 ms |
2864 KB |
Output is correct |
23 |
Correct |
21 ms |
3404 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 |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
380 KB |
Output is correct |
9 |
Correct |
1 ms |
372 KB |
Output is correct |
10 |
Correct |
4 ms |
596 KB |
Output is correct |
11 |
Correct |
28 ms |
3300 KB |
Output is correct |
12 |
Correct |
439 ms |
53432 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
16 ms |
2644 KB |
Output is correct |
18 |
Correct |
385 ms |
56836 KB |
Output is correct |
19 |
Correct |
397 ms |
57252 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
5 ms |
980 KB |
Output is correct |
25 |
Correct |
16 ms |
2316 KB |
Output is correct |
26 |
Correct |
15 ms |
2260 KB |
Output is correct |
27 |
Correct |
437 ms |
60252 KB |
Output is correct |
28 |
Correct |
0 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
340 KB |
Output is correct |
31 |
Correct |
2 ms |
468 KB |
Output is correct |
32 |
Correct |
23 ms |
2536 KB |
Output is correct |
33 |
Correct |
4 ms |
724 KB |
Output is correct |
34 |
Correct |
5 ms |
852 KB |
Output is correct |
35 |
Correct |
576 ms |
54260 KB |
Output is correct |
36 |
Correct |
529 ms |
50624 KB |
Output is correct |
37 |
Correct |
526 ms |
50736 KB |
Output is correct |
38 |
Correct |
589 ms |
54404 KB |
Output is correct |
39 |
Correct |
0 ms |
340 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 |
536 KB |
Output is correct |
43 |
Correct |
2 ms |
468 KB |
Output is correct |
44 |
Correct |
2 ms |
468 KB |
Output is correct |
45 |
Correct |
0 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 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 |
596 KB |
Output is correct |
51 |
Correct |
19 ms |
3352 KB |
Output is correct |
52 |
Correct |
20 ms |
3324 KB |
Output is correct |
53 |
Correct |
21 ms |
3276 KB |
Output is correct |
54 |
Correct |
23 ms |
3372 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 |
520 KB |
Output is correct |
58 |
Correct |
19 ms |
2808 KB |
Output is correct |
59 |
Correct |
20 ms |
3340 KB |
Output is correct |
60 |
Correct |
19 ms |
2864 KB |
Output is correct |
61 |
Correct |
21 ms |
3404 KB |
Output is correct |
62 |
Correct |
52 ms |
8552 KB |
Output is correct |
63 |
Correct |
51 ms |
8444 KB |
Output is correct |
64 |
Correct |
64 ms |
8688 KB |
Output is correct |
65 |
Correct |
227 ms |
33284 KB |
Output is correct |
66 |
Correct |
257 ms |
33732 KB |
Output is correct |
67 |
Correct |
5 ms |
1108 KB |
Output is correct |
68 |
Correct |
4 ms |
852 KB |
Output is correct |
69 |
Correct |
460 ms |
73300 KB |
Output is correct |
70 |
Correct |
479 ms |
74456 KB |
Output is correct |
71 |
Correct |
587 ms |
76132 KB |
Output is correct |
72 |
Correct |
463 ms |
63716 KB |
Output is correct |
73 |
Correct |
522 ms |
76048 KB |
Output is correct |
74 |
Correct |
421 ms |
60980 KB |
Output is correct |
75 |
Correct |
491 ms |
73640 KB |
Output is correct |