Cod sursa(job #2155745)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 martie 2018 02:35:52
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 50050
int d1[N],x,y,curr,d2[N],X[N],Y[N],n,i,j,dim,ax=999999,ay=999999;
int main()
{
    ifstream f("tribute.in");
    f>>n>>x>>y;
    for(i=0;i<n;++i)
        f>>X[i]>>Y[i];
    sort(X,X+n);
    sort(Y,Y+n);
    dim=max(X[n-1],Y[n-1])+1;
    while(j<n && X[j]<1)++j,++d1[0];
    for(i=1;i<dim;++i)
    {
        curr=0;
        while(j<n && X[j]<=i)
            ++j,++curr;
        d1[i]=d1[i-1]+curr;
    }
    j=n-1;
    for(i=dim;i>-1;--i)
    {
        curr=0;
        while(j>-1 && X[j]>=i)
            --j,++curr;
        d2[i]=d2[i+1]+curr;
    }
    for(i=0;i<dim-x;++i)
        ax=min(ax,d1[i]+d2[i+x]);
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));
    j=0;while(j<n && Y[j]<1)++j,++d1[0];
    for(i=1;i<dim;++i)
    {
        curr=0;
        while(j<n && Y[j]<=i)
            ++j,++curr;
        d1[i]=d1[i-1]+curr;
    }
    j=n-1;
    for(i=dim;i>-1;--i)
    {
        curr=0;
        while(j>-1 && Y[j]>=i)
            --j,++curr;
        d2[i]=d2[i+1]+curr;
    }
    for(i=0;i<dim-y;++i)
        ay=min(ay,d1[i]+d2[i+y]);
    ofstream g("tribute.out");
    g<<ax+ay;
    return 0;
}