Cod sursa(job #2526574)

Utilizator RedXtreme45Catalin RedXtreme45 Data 18 ianuarie 2020 20:09:38
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define Nmax 100003
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
int n,dx,dy;
int x[Nmax],y[Nmax],S;
void rezolvare (int c[]){
    int lim=c[n]+c[0]+1;
    int st[Nmax],dr[Nmax];
    memset(st,0,sizeof st);
    memset(dr,0,sizeof dr);
    int j=1,nr=0;
    for (int i=0;i<=lim;i++)
    {
        if (i>0)
        st[i]+=st[i-1]+nr;
        while (c[j]==i && j<=n)
        {
            nr++;
            j++;
        }
    }
    j=n,nr=0;
    for (int i=lim;i>=0;i--)
    {
        dr[i]+=dr[i+1]+nr;
        while (c[j]==i && j>=1)
        {
            nr++;
            j--;
        }
    }
    int sol=1000000000;
    lim-=c[0];
    for (int i=0;i<=lim;i++)
    {
        sol=min(st[i]+dr[i+c[0]],sol);
    }
    S+=sol;
}
int main()
{
    int i;
    fin>>n>>dx>>dy;
    for (i=1;i<=n;i++)
    {
        fin>>x[i]>>y[i];
    }
    sort (x+1,x+n+1);
    sort (y+1,y+n+1);
    x[0]=dx;
    y[0]=dy;
    rezolvare(x);
    rezolvare(y);
    fout<<S;
    return 0;
}