Cod sursa(job #3209960)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 4 martie 2024 08:36:40
Problema Wanted Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <math.h>
#include <algorithm>

#define fi first
#define sc second
#define mp make_pair

using namespace std;
typedef pair<int, int> pii;
const int N = 205;

int n;
pii v[N];

int dist(pii a, pii b) {
    return abs(a.fi - b.fi) + abs(a.sc) + abs(b.sc);
}
int solve(int crt, int st, int dr, int cost) {
    if(st == dr)
        return cost;
    else {
        int mid1 = (st + crt) / 2;
        int mid2 = (crt + 1 + dr) / 2;

        return max(solve(mid1, st, crt, cost + dist(v[crt], v[mid1])),
                   solve(mid2, crt+1, dr, cost + dist(v[crt], v[mid2])));
    }
}

int main()
{
    freopen("wanted.in", "r", stdin);
    freopen("wanted.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> v[i].fi >> v[i].sc;

    sort(v+1, v+n+1, [&](pii a, pii b) {
        if(a.fi != b.fi)
            return a.fi < b.fi;
        else return a.sc > b.sc;
    });

    cout << solve((1 + n) / 2, 1, n, dist(mp(0, 0), v[(1+n)/2]));
    return 0;
}