#include <bits/stdc++.h>
//#include "tickets.h"
using namespace std;
void allocate_tickets(vector<vector<int>>);
typedef pair<int,int> P;
long long find_maximum(int k, vector<vector<int> > x) {
int N = x.size();
int M = x[0].size();
vector<vector<int> > ans;
ans.resize(N);
int i,j;
for(i=0;i<N;i++) {
ans[i].resize(M);
fill(ans[i].begin(),ans[i].end(),-1);
}
long long int cnt = 0;
if(k==1) {
vector<int> pt1;
vector<int> pt2;
pt1.resize(N);
pt2.resize(N);
fill(pt2.begin(),pt2.end(),M-1);
int j, st;
for(j=0;j<k;j++) {
vector<P> V;
for(i=0;i<N;i++) {
V.push_back(P(x[i][pt2[i]]+x[i][pt1[i]],i));
}
sort(V.begin(),V.end());
for(i=0;i<N;i++) {
int n = V[i].second;
if(i < N / 2) {
ans[n][pt1[n]] = j;
cnt -= x[n][pt1[n]];
pt1[n]++;
}
else {
ans[n][pt2[n]] = j;
cnt += x[n][pt2[n]];
pt2[n]--;
}
}
}
allocate_tickets(ans);
return cnt;
}
else {
vector<P> A;
A.resize(N);
for(i=0;i<N;i++) {
for(j=0;j<M;j++) {
A[i].first += x[i][j];
}
A[i].second = i;
}
vector<int> pt1;
vector<int> pt2;
pt1.resize(N);
pt2.resize(N);
fill(pt2.begin(),pt2.end(),M-1);
sort(A.begin(),A.end(),[](P x, P y) {return x.first > y.first;});
for(i=0;i<k;i++) {
for(j=0;j<N;j++) {
if(j < N/2) {
ans[A[j].second][pt2[A[j].second]] = i;
cnt += x[A[j].second][pt2[A[j].second]];
A[j].first -= x[A[j].second][pt2[A[j].second]];
pt2[A[j].second]--;
}
else {
ans[A[j].second][pt1[A[j].second]] = i;
cnt -= x[A[j].second][pt1[A[j].second]];
A[j].first -= x[A[j].second][pt1[A[j].second]];
pt1[A[j].second]++;
}
}
sort(A.begin(),A.end(),[](P x, P y) {return x.first > y.first;});
}
allocate_tickets(ans);
return cnt;
}
}
Compilation message
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:26:16: warning: unused variable 'st' [-Wunused-variable]
26 | int j, st;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
26 ms |
2340 KB |
Output is correct |
6 |
Correct |
692 ms |
51448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
23 ms |
2380 KB |
Output is correct |
6 |
Correct |
568 ms |
52264 KB |
Output is correct |
7 |
Correct |
582 ms |
52704 KB |
Output is correct |
8 |
Correct |
3 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
6 ms |
716 KB |
Output is correct |
13 |
Correct |
19 ms |
2024 KB |
Output is correct |
14 |
Correct |
20 ms |
1952 KB |
Output is correct |
15 |
Correct |
587 ms |
57820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Contestant returned 24037843666 while correct return value is 24057831018. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Incorrect |
3 ms |
460 KB |
Contestant returned 188951282355 while correct return value is 191909121109. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
460 KB |
Output is correct |
3 |
Incorrect |
3 ms |
460 KB |
Contestant returned 188951282355 while correct return value is 191909121109. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
26 ms |
2340 KB |
Output is correct |
12 |
Correct |
692 ms |
51448 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
23 ms |
2380 KB |
Output is correct |
18 |
Correct |
568 ms |
52264 KB |
Output is correct |
19 |
Correct |
582 ms |
52704 KB |
Output is correct |
20 |
Correct |
3 ms |
460 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
6 ms |
716 KB |
Output is correct |
25 |
Correct |
19 ms |
2024 KB |
Output is correct |
26 |
Correct |
20 ms |
1952 KB |
Output is correct |
27 |
Correct |
587 ms |
57820 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Incorrect |
1 ms |
204 KB |
Contestant returned 24037843666 while correct return value is 24057831018. |
31 |
Halted |
0 ms |
0 KB |
- |