Cod sursa(job #2467110)

Utilizator bluestorm57Vasile T bluestorm57 Data 3 octombrie 2019 18:39:01
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.14 kb
//wish me luck
//I'm ready for tle/wrong answer
#include <bits/stdc++.h>

using namespace std;

ifstream f("tribute.in");
ofstream g("tribute.out");

const int NMAX = 50005;
const int inf = 1e9;
struct Pair{
    int x,y,id;
}point[NMAX];
int n,dx,dy,ans;
int dp[NMAX],dp2[NMAX];
int dpx2[NMAX], dpx3[NMAX];
int dpy2[NMAX], dpy3[NMAX];

void see(int v[]){
    int i;
    for(i = 1 ; i <= n ; i++)
        g << v[i] << " ";
    g << "\n";
}

bool cmp1(Pair X, Pair Y){
    return X.y < Y.y;
}

bool cmp2(Pair X, Pair Y){
    return X.x < Y.x;
}

void up_y(int dpy[]){
    int i,j,value,dif;
    j = 1;
    dp2[n] = 0;
    for(i = n - 1 ; i >= 1 ; i--, j++){
        dp2[i] = dp2[i + 1] + (point[i + 1].y - point[i].y) * j;
    }

    dp[1] = 0;
    for(i = 2 ; i <= n ; i++){
        dp[i] = 0;
        value = point[i].y - dy;
        for(j = i - 1 ; j >= 1 ; j--){
            dif = value - point[j].y;
            if(dif > 0)
                dp[i] += dif;
        }
    }
    for(i = 1 ; i <= n ; i++)
        dpy[i] = dp[i] + dp2[i];
}

void down_y(int dpy[]){
    int i,j,value,dif;
    dp[1] = 0;
    for(i = 2 ; i <= n ; i++)
        dp[i] = dp[i - 1] + (point[i].y - point[i - 1].y) * (i - 1);

    dp2[n] = 0;
    for(i = n - 1 ; i >= 1 ; i--){
        dp2[i] = 0;
        value = point[i].y + dy;
        for(j = i + 1 ; j <= n ; j++){
            dif = point[j].y - value;
            if(dif > 0)
                dp2[i] += dif;
        }

    }
    for(i = 1 ; i <= n ; i++)
        dpy[i] = dp[i] + dp2[i];
}

void left_x(int dpx[]){
    int i,j,value,dif;
    dp[1] = 0;
    for(i = 1 ; i <= n ; i++)
        dp[i] = dp[i - 1] + (point[i].x - point[i - 1].x) * (i - 1);
    dp2[n] = 0;
    for(i = n - 1 ; i >= 1 ; i--){
        dp2[i] = 0;
        value = point[i].x + dx;
        for(j = i + 1 ; j <= n ; j++){
            dif = point[j].x - value;
            if(dif > 0)
                dp2[i] += dif;
        }
    }
    for(i = 1 ; i <= n ; i++)
        dpx[i] = dp[i] + dp2[i];
}

void right_x(int dpx[]){
    int i,j,dif,value;
    dp[1] = 0;
    for(i = 2 ; i <= n ; i++){
        dp[i] = 0;
        value = point[i].x - dx;
        for(j = i - 1 ; j >= 1 ; j--){
            dif = value - point[j].x;
            if(dif > 0)
                dp[i] += dif;
        }
    }

    j = 1;
    dp2[n] = 0;
    for(i = n - 1 ; i >= 1 ; i--, j++)
        dp2[i] = dp2[i + 1] + (point[i + 1].x - point[i].x) * j;

    for(i = 1 ; i <= n ; i++)
        dpx[i] = dp[i] + dp2[i];
}

int main(){
    int i;
    f >> n >> dx >> dy;
    for(i = 1 ; i <= n ; i++){
        f >> point[i].x >> point[i].y;
        point[i].id = i;
    }

    ///y
    sort(point + 1, point + n + 1, cmp1);
    up_y(dpy2);
    down_y(dpy3);

    ///x;
    sort(point + 1, point + n + 1, cmp2);
    left_x(dpx2);
    right_x(dpx3);

    ans = inf;
    for(i = 1 ; i <= n ; i++){
        ans = min(ans, dpx2[i] + dpy2[i]);
        ans = min(ans, dpx2[i] + dpy3[i]);
        ans = min(ans, dpx3[i] + dpy2[i]);
        ans = min(ans, dpx3[i] + dpy3[i]);
    }
    g << ans;
    return 0;
}