Cod sursa(job #3317699)

Utilizator Iustin.DDragusanu Iustin Iustin.D Data 24 octombrie 2025 22:58:12
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <vector>
using namespace std;

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

#define int long long

int n,dx,dy;
vector<int>x(50005);
vector<int>y(50005);

int solve(vector<int>&v,int dn)
{
    int mx=0;
    vector<int>freq(50005);
    for (int i=0; i<n; i++)
    {
        if (v[i]>mx) mx=v[i];
        freq[v[i]]++;
    }
    if (dn>=mx) return 0;
    vector<int>cost_left(mx+5);
    vector<int>cost_right(mx+5);
    int cnt=0;
    //cost_left[0]=freq[0];
    for (int i=1; i<=mx; i++)
    {
        cost_left[i]=cost_left[i-1]+cnt;
        cnt+=freq[i-1];
    }
    cnt=0;
    //cost_right[mx+1]=0;
    for (int i=mx; i>=0; i--)
    {
        cost_right[i]=cost_right[i+1]+cnt;
        cnt+=freq[i];
    }
    int mn=1000000000000000;
    for (int i=dn-1; i<=mx; i++)
    {
        //cout<<i-dn+1<<"|"<<cost_left[i-dn+1]<<" "<<i<<"|"<<cost_right[i]<<"\n";
        if (cost_left[i-dn+1]+cost_right[i]<mn) mn=cost_left[i-dn+1]+cost_right[i];
    }
    //cout<<"\n";
    return mn;
}

int32_t main()
{
    cin>>n>>dx>>dy;
    for (int i=0; i<n; i++) cin>>x[i]>>y[i];
    //cout<<"\n\n";
    cout<<solve(x,dx)+solve(y,dy);
}