oj.uz

Submission #487444

# Submission time Handle Problem Language Result Execution time Memory
487444 2021-11-15T14:24:40 Z KienTran Best Place (NOI17_bestplace) C++14
100 / 100
 36 ms 3444 KB 
#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(){
      | ^~~~

Subtask #1
3.0 / 3.0

# 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

Subtask #2
20.0 / 20.0

# 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

Subtask #3
28.0 / 28.0

# 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

Subtask #4
13.0 / 13.0

# 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

Subtask #5
17.0 / 17.0

# 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

Subtask #6
19.0 / 19.0

# 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