Cod sursa(job #3317448)

Utilizator mtcmtcmtc mtc mtcmtc Data 23 octombrie 2025 17:26:39
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <vector>
#include <climits>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
ifstream cin("tribute.in");
ofstream cout("tribute.out");
int solve(vector<int>&X,int dx){
    int ret=0;
    int max_coord=*max_element(X.begin(),X.end());
    vector<int>cost_le(max_coord+1),cost_ri(max_coord+1);
    vector<int>freq(max_coord+1);
    for(auto x:X){
        freq[x]++;
    }
    int cnt=freq[0];
    for(int i=1;i<=max_coord;i++){
        cost_le[i]=cost_le[i-1]+cnt;
        cnt+=freq[i];
    }
    cnt=freq[max_coord];
    for(int i=max_coord-1;i>=0;i--){
        cost_ri[i]=cost_ri[i+1]+cnt;
        cnt+=freq[i];
    }
    ret=LLONG_MAX;
    for(int i=0;i<=max_coord-dx;i++){
        ret=min(ret,cost_le[i]+cost_ri[i+dx]);
    }
    if(dx>max_coord) ret=0;
    return ret;
}
int32_t main()
{
    int n,dx,dy;
    cin>>n>>dx>>dy;
    vector<int>x(n),y(n);
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i];
    }
    cout<<solve(x,dx)+solve(y,dy)<<'\n';
    return 0;
}