Cod sursa(job #2933834)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 5 noiembrie 2022 13:21:43
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=5e4+1;
int n,dx,dy,a,b;
int y[nmax+4],x[nmax+4],stanga,dreapta,disty,distx;

int main()
{
    fin>>n>>dx>>dy;
    for(int i=0; i<n; i++)
    {
        fin>>a>>b;
        x[a]++;
        distx+=a;
        y[b]++;
        disty+=b;
    }

    stanga=0;
    dreapta=n;

    dreapta-=x[0];
    int distxmin=distx;
    for(int i=1; i<nmax && stanga<=dreapta; i++)
    {
        //cout<<distx<<" "<<stanga<<" "<<dreapta<<"\n";
        distx-=dreapta;
        dreapta-=x[i];
        distx+=stanga;
        if(i>=dx) stanga+=x[i-dx];
        distxmin=min(distx,distxmin);
    }
    stanga=0;
    dreapta=n;

    dreapta-=y[0];
    int distymin=disty;
    for(int i=1; i<nmax && stanga<=dreapta; i++)
    {
        //cout<<disty<<" "<<stanga<<" "<<dreapta<<"\n";
        disty-=dreapta;
        dreapta-=y[i];
        disty+=stanga;
        if(i>=dy) stanga+=y[i-dy];
        distymin=min(disty,distymin);
    }
    fout<<distxmin+distymin;
    return 0;
}