Cod sursa(job #3327052)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 2 decembrie 2025 01:23:35
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

bool desc(int a,int b)
{
    return a>b;
}
long long x[50005],y[50005],prefx[50005],prefy[50005],mnx = 1e18, mny = 1e18;
int j=1;
int main()
{
    int n,dx,dy;
    fin>>n>>dx>>dy;
    for(int i=1;i<=n;i++)
    {
        fin>>x[i]>>y[i];
    }
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++)
    {
        prefx[i]=prefx[i-1]+x[i];
    }
    sort(y+1,y+n+1);
    for(int i=1;i<=n;i++)
    {
        prefy[i]=prefy[i-1]+y[i];
    }
     for(int i=1;i<=n;i++)
    {

        while(j+1<=n && x[j+1]<=x[i]+dx-1)
            j++;
        long long cost_st,cost_dr,cost_tot;
        cost_st=x[i]*(i-1)-prefx[i-1];
        cost_dr=(prefx[n]-prefx[j])-(x[i]+dx)*(n-j);
        cost_tot=cost_st+cost_dr;
        //cout<<i<<" "<<j<<" "<<x[i]<<" "<<x[j]<<" "<<cost_tot<<endl;
        if(cost_tot<mnx)
            mnx=cost_tot;

    }
    j=1;
    sort(x+1,x+n+1,desc);
    for(int i=1;i<=n;i++)
    {
        prefx[i]=prefx[i-1]+x[i];
    }
     for(int i=1;i<=n;i++)
    {

        while(j+1<=n && x[j+1]>=x[i]-dx+1)
            j++;
        long long cost_st,cost_dr,cost_tot;
        cost_st=-(x[i]*(i-1)-prefx[i-1]);
        cost_dr=-((prefx[n]-prefx[j])-(x[i]-dx)*(n-j));
        cost_tot=cost_st+cost_dr;
        //cout<<i<<" "<<j<<" "<<x[i]<<" "<<x[j]<<" "<<cost_tot<<endl;
        if(cost_tot<mnx)
            mnx=cost_tot;

    }
    j=1;
    for(int i=1;i<=n;i++)
    {

        while(j+1<=n && y[j+1]<=y[i]+dy-1)
            j++;
        long long cost_st,cost_dr,cost_tot;
        cost_st=y[i]*(i-1)-prefy[i-1];
        cost_dr=(prefy[n]-prefy[j])-(y[i]+dy)*(n-j);
        cost_tot=cost_st+cost_dr;
        if(cost_tot<mny)
            mny=cost_tot;

    }
    j=1;
    sort(y+1,y+n+1,desc);
    for(int i=1;i<=n;i++)
    {
        prefy[i]=prefy[i-1]+y[i];
    }
     for(int i=1;i<=n;i++)
    {

        while(j+1<=n && y[j+1]>=y[i]-dy+1)
            j++;
        long long cost_st,cost_dr,cost_tot;
        cost_st=-(y[i]*(i-1)-prefy[i-1]);
        cost_dr=-((prefy[n]-prefy[j])-(y[i]-dy)*(n-j));
        cost_tot=cost_st+cost_dr;
        if(cost_tot<mny)
            mny=cost_tot;

    }
    fout<<mnx+mny;
    return 0;
}