#include <bits/stdc++.h>
#define int long long
using namespace std;
const int O = 1e5 + 5;
const int inf = 1e18;
int n, a[O], b[O], sumA[O], sumB[O];
int solban(){
int res = inf;
for (int i = 1; i <= 100; ++ i){
for (int j = 1; j <= 100; ++ j){
int cost = 0;
for (int z = 1; z <= n; ++ z){
cost += abs(a[z] - i) + abs(b[z] - j);
}
res = min(res, cost);
}
}
return res;
}
main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); srand(time(NULL));
cin >> n;
for (int i = 1; i <= n; ++ i){
cin >> a[i] >> b[i];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; ++ i){
sumA[i] = sumA[i - 1] + a[i];
sumB[i] = sumB[i - 1] + b[i];
}
int Max = inf, X = 0;
for (int i = 1; i <= n; ++ i){
int cost = a[i] * i - sumA[i] + sumA[n] - sumA[i] - a[i] * (n - i);
if (cost < Max){
Max = cost;
X = a[i];
}
}
Max = inf;
int Y = 0;
for (int i = 1; i <= n; ++ i){
int cost = b[i] * i - sumB[i] + sumB[n] - sumB[i] - b[i] * (n - i);
if (cost < Max){
Max = cost;
Y = b[i];
}
}
int res = 0;
for (int i = 1; i <= n; ++ i) res += abs(X - a[i]) + abs(Y - b[i]);
cout << X << " " << Y;
}
Compilation message
bestplace.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
26 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3436 KB |
Output is correct |
2 |
Correct |
23 ms |
3404 KB |
Output is correct |
3 |
Correct |
24 ms |
3444 KB |
Output is correct |
4 |
Correct |
22 ms |
3392 KB |
Output is correct |
5 |
Correct |
20 ms |
3404 KB |
Output is correct |
6 |
Correct |
23 ms |
3332 KB |
Output is correct |
7 |
Correct |
22 ms |
3372 KB |
Output is correct |
8 |
Correct |
23 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
3344 KB |
Output is correct |
2 |
Correct |
35 ms |
3416 KB |
Output is correct |
3 |
Correct |
22 ms |
3404 KB |
Output is correct |
4 |
Correct |
36 ms |
3424 KB |
Output is correct |
5 |
Correct |
32 ms |
3364 KB |
Output is correct |
6 |
Correct |
32 ms |
3392 KB |
Output is correct |
7 |
Correct |
31 ms |
3420 KB |
Output is correct |
8 |
Correct |
33 ms |
3424 KB |
Output is correct |