#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1505
#define MAXM 1505
ll ans;
int type[MAXN][MAXM];//0=unused,-1='-',1='+'
int val[MAXN][MAXM];
priority_queue<int> q_col_minus[MAXN];//by color -> pos
priority_queue<int> q_col_unused[MAXN];
priority_queue<pair<ll,int>> q_gen;//general -> (num,col)
vector<vector<int>> answer;
vector<int> plus_[MAXN];
vector<int> minus_[MAXN];
bool changeable(int col){
return !q_col_minus[col].empty();
}
ll res(int col){
if(q_col_unused[col].empty()) return 2*val[col][q_col_minus[col].top()];
else return val[col][q_col_minus[col].top()]+val[col][max(q_col_unused[col].top(),q_col_minus[col].top())];
}
void change(int col){
ans+=res(col);
if(q_col_unused[col].empty()){
int pos=q_col_minus[col].top();
q_col_minus[col].pop();
type[col][pos]=1;
}else{
int pos_minus=q_col_minus[col].top();
int pos_unused=q_col_unused[col].top();
if(pos_minus<pos_unused){
q_col_minus[col].pop();
q_col_unused[col].pop();
type[col][pos_minus]=0;
q_col_unused[col].push(pos_minus);
type[col][pos_unused]=1;
}else{
q_col_minus[col].pop();
type[col][pos_minus]=1;
}
}
q_gen.pop();
if(changeable(col)) q_gen.push({res(col),col});
}
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
ans=0;
for(int col=0;col<n;col++){
answer.push_back(vector<int>(m,-1));
for(int pos=0;pos<m;pos++){
val[col][pos]=x[col][pos];
if(pos<k){
q_col_minus[col].push(pos);
type[col][pos]=-1;
ans-=val[col][pos];
}
else{
q_col_unused[col].push(pos);
type[col][pos]=0;
}
}
if(changeable(col)) q_gen.push({res(col),col});
}
for(int round=0;round<k*n/2;round++){//rounds in greedy algorithm
change(q_gen.top().second);
}
for(int col=0;col<n;col++){
for(int pos=0;pos<m;pos++){
if(type[col][pos]==1) plus_[col].push_back(pos);
else if(type[col][pos]==-1) minus_[col].push_back(pos);
}
}
for(int round=0;round<k;round++){
vector<pair<int,int>> pluses;
for(int col=0;col<n;col++){
pluses.push_back({plus_[col].size(),col});
}
sort(pluses.begin(),pluses.end(),greater<pair<int,int>>());
for(int i=0;i<n;i++){
int col=pluses[i].second;
if(i<n/2){
answer[col][plus_[col].back()]=round;
plus_[col].pop_back();
}else{
answer[col][minus_[col].back()]=round;
minus_[col].pop_back();
}
}
}
allocate_tickets(answer);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
3 ms |
3052 KB |
Output is correct |
6 |
Correct |
9 ms |
13020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
3 ms |
1384 KB |
Output is correct |
5 |
Correct |
39 ms |
7060 KB |
Output is correct |
6 |
Correct |
731 ms |
103168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
33 ms |
6664 KB |
Output is correct |
6 |
Correct |
874 ms |
92708 KB |
Output is correct |
7 |
Correct |
916 ms |
93100 KB |
Output is correct |
8 |
Correct |
5 ms |
1612 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
10 ms |
2516 KB |
Output is correct |
13 |
Correct |
38 ms |
7624 KB |
Output is correct |
14 |
Correct |
30 ms |
4804 KB |
Output is correct |
15 |
Correct |
1018 ms |
102536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
4 ms |
1356 KB |
Output is correct |
5 |
Correct |
47 ms |
7788 KB |
Output is correct |
6 |
Correct |
8 ms |
1228 KB |
Output is correct |
7 |
Correct |
16 ms |
13492 KB |
Output is correct |
8 |
Correct |
1433 ms |
118028 KB |
Output is correct |
9 |
Correct |
1320 ms |
113052 KB |
Output is correct |
10 |
Correct |
1244 ms |
110176 KB |
Output is correct |
11 |
Correct |
1386 ms |
118208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
3 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
4 ms |
1356 KB |
Output is correct |
6 |
Correct |
4 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
1100 KB |
Output is correct |
9 |
Correct |
3 ms |
1356 KB |
Output is correct |
10 |
Correct |
4 ms |
1356 KB |
Output is correct |
11 |
Correct |
4 ms |
1356 KB |
Output is correct |
12 |
Correct |
4 ms |
1356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
3 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
4 ms |
1356 KB |
Output is correct |
6 |
Correct |
4 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
1100 KB |
Output is correct |
9 |
Correct |
3 ms |
1356 KB |
Output is correct |
10 |
Correct |
4 ms |
1356 KB |
Output is correct |
11 |
Correct |
4 ms |
1356 KB |
Output is correct |
12 |
Correct |
4 ms |
1356 KB |
Output is correct |
13 |
Correct |
30 ms |
7036 KB |
Output is correct |
14 |
Correct |
34 ms |
7108 KB |
Output is correct |
15 |
Correct |
47 ms |
7480 KB |
Output is correct |
16 |
Correct |
48 ms |
7688 KB |
Output is correct |
17 |
Correct |
2 ms |
588 KB |
Output is correct |
18 |
Correct |
5 ms |
3148 KB |
Output is correct |
19 |
Correct |
3 ms |
3020 KB |
Output is correct |
20 |
Correct |
37 ms |
6648 KB |
Output is correct |
21 |
Correct |
39 ms |
7020 KB |
Output is correct |
22 |
Correct |
48 ms |
6976 KB |
Output is correct |
23 |
Correct |
42 ms |
7384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
1100 KB |
Output is correct |
5 |
Correct |
3 ms |
3052 KB |
Output is correct |
6 |
Correct |
9 ms |
13020 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
3 ms |
1384 KB |
Output is correct |
11 |
Correct |
39 ms |
7060 KB |
Output is correct |
12 |
Correct |
731 ms |
103168 KB |
Output is correct |
13 |
Correct |
1 ms |
588 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
3 ms |
1356 KB |
Output is correct |
17 |
Correct |
33 ms |
6664 KB |
Output is correct |
18 |
Correct |
874 ms |
92708 KB |
Output is correct |
19 |
Correct |
916 ms |
93100 KB |
Output is correct |
20 |
Correct |
5 ms |
1612 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
22 |
Correct |
1 ms |
460 KB |
Output is correct |
23 |
Correct |
1 ms |
460 KB |
Output is correct |
24 |
Correct |
10 ms |
2516 KB |
Output is correct |
25 |
Correct |
38 ms |
7624 KB |
Output is correct |
26 |
Correct |
30 ms |
4804 KB |
Output is correct |
27 |
Correct |
1018 ms |
102536 KB |
Output is correct |
28 |
Correct |
1 ms |
460 KB |
Output is correct |
29 |
Correct |
1 ms |
460 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
4 ms |
1356 KB |
Output is correct |
32 |
Correct |
47 ms |
7788 KB |
Output is correct |
33 |
Correct |
8 ms |
1228 KB |
Output is correct |
34 |
Correct |
16 ms |
13492 KB |
Output is correct |
35 |
Correct |
1433 ms |
118028 KB |
Output is correct |
36 |
Correct |
1320 ms |
113052 KB |
Output is correct |
37 |
Correct |
1244 ms |
110176 KB |
Output is correct |
38 |
Correct |
1386 ms |
118208 KB |
Output is correct |
39 |
Correct |
1 ms |
460 KB |
Output is correct |
40 |
Correct |
3 ms |
1356 KB |
Output is correct |
41 |
Correct |
3 ms |
1356 KB |
Output is correct |
42 |
Correct |
3 ms |
1356 KB |
Output is correct |
43 |
Correct |
4 ms |
1356 KB |
Output is correct |
44 |
Correct |
4 ms |
1356 KB |
Output is correct |
45 |
Correct |
1 ms |
588 KB |
Output is correct |
46 |
Correct |
1 ms |
1100 KB |
Output is correct |
47 |
Correct |
3 ms |
1356 KB |
Output is correct |
48 |
Correct |
4 ms |
1356 KB |
Output is correct |
49 |
Correct |
4 ms |
1356 KB |
Output is correct |
50 |
Correct |
4 ms |
1356 KB |
Output is correct |
51 |
Correct |
30 ms |
7036 KB |
Output is correct |
52 |
Correct |
34 ms |
7108 KB |
Output is correct |
53 |
Correct |
47 ms |
7480 KB |
Output is correct |
54 |
Correct |
48 ms |
7688 KB |
Output is correct |
55 |
Correct |
2 ms |
588 KB |
Output is correct |
56 |
Correct |
5 ms |
3148 KB |
Output is correct |
57 |
Correct |
3 ms |
3020 KB |
Output is correct |
58 |
Correct |
37 ms |
6648 KB |
Output is correct |
59 |
Correct |
39 ms |
7020 KB |
Output is correct |
60 |
Correct |
48 ms |
6976 KB |
Output is correct |
61 |
Correct |
42 ms |
7384 KB |
Output is correct |
62 |
Correct |
85 ms |
15428 KB |
Output is correct |
63 |
Correct |
101 ms |
15604 KB |
Output is correct |
64 |
Correct |
131 ms |
16992 KB |
Output is correct |
65 |
Correct |
493 ms |
51628 KB |
Output is correct |
66 |
Correct |
606 ms |
54428 KB |
Output is correct |
67 |
Correct |
17 ms |
13480 KB |
Output is correct |
68 |
Correct |
7 ms |
1224 KB |
Output is correct |
69 |
Correct |
760 ms |
103344 KB |
Output is correct |
70 |
Correct |
1092 ms |
106308 KB |
Output is correct |
71 |
Correct |
1431 ms |
117888 KB |
Output is correct |
72 |
Correct |
1117 ms |
102868 KB |
Output is correct |
73 |
Correct |
1355 ms |
113792 KB |
Output is correct |
74 |
Correct |
934 ms |
95088 KB |
Output is correct |
75 |
Correct |
1112 ms |
106392 KB |
Output is correct |