Cod sursa(job #3364437)

Utilizator CarenaMironov Cezar Luca Carena Data 3 septembrie 2026 14:24:13
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define int long long

using namespace std;

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

const int INF=1e18;
int n, dx, dy;
vector<int> vx, vy, sx, sy;

int get_dist(vector<int> &v, vector<int> &sp, int l)
{
    int ans=INF, j=0;
    for(int i=1;i<=n;i++)
    {
        while(v[j+1]<v[i]-l)
            j++;
        ans=min(ans, (j*(v[i]-l) - sp[j]) + (sp[n]-sp[i-1] - (n-i+1)*v[i]));
    }
    
    j=1;
    for(int i=1;i<=n;i++)
    {
        while(j<=n && v[j]<=v[i]+l)
            j++;
        ans=min(ans, (i*v[i] - sp[i]) + (sp[n]-sp[j-1] - (n-j+1)*(v[i]+l)));
    }
    
    return ans;
}

signed main()
{
    in>>n>>dx>>dy;
    vx.resize(n+1); sx.resize(n+1);
    vy.resize(n+1); sy.resize(n+1);
    for(int i=1;i<=n;i++)
        in>>vx[i]>>vy[i];
    
    sort(next(vx.begin()), vx.end());
    sort(next(vy.begin()), vy.end());
    for(int i=1;i<=n;i++)
    {
        sx[i]=sx[i-1]+vx[i];
        sy[i]=sy[i-1]+vy[i];
    }
    
    out<<get_dist(vx, sx, dx)+get_dist(vy, sy, dy);
    return 0;
}