#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define what_is(a) cout << #a << " is " << a << "\n"
using namespace std;
ll diff(int val,vector<int> vec){
ll r = 0;
for(int a:vec){
r += abs(a-val);
//cout << abs(a-val) << " ";
}
//cout << "\n";
return r;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
assert(m==1);
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m,0);
answer.push_back(row);
}
allocate_tickets(answer);
ll lo =0,hi=1000000000;
vector<int> vec;
for(int i=0;i<n;i++)
vec.push_back(x[i][0]);
while(lo<hi){
ll l1 = lo + (hi-lo)/3,l2=hi - (hi-lo)/3;
ll a = diff(l1,vec),b=diff(l2,vec);
if(a==b)break;
if(a<b){
hi = l2;
}else{
lo = l1;
}
}
//what_is(lo);
//what_is(hi);
return diff((lo+hi)/2,vec);
}
# |
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 |
1 ms |
296 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 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
1 ms |
296 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
8 |
Halted |
0 ms |
0 KB |
- |