Cod sursa(job #122028)

Utilizator igorPirnau Igor igor Data 10 ianuarie 2008 17:56:38
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<fstream.h>

ifstream f("tribute.in");
ofstream g("tribute.out");

#define lim 50100
#define inf 1000000000

unsigned int st[lim], dr[lim], st1[lim], dr1[lim],n ,i, x, y, dx, dy, a[lim], b[lim];
long sum, min, miny;


int main()
{
    f>>n>>dx>>dy;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        a[x]=1;
        b[y]=1;
    }
    f.close();

    sum=0;
    for(i=1;i<=lim;i++)
    {
        st[i]=st[i-1]+sum;
        sum=sum+a[i];
    }
    
    sum=0;
    for(i=lim;i>0;i--)
    {
        dr[i]=dr[i+1]+sum;
        sum=sum+a[i];
    }

    min=inf;
    for(i=1;i<=lim-dx+1;i++) if(st[i]+dr[i+dx-1]<min) min=st[i]+dr[i+dx-1];
 
    sum=0;
    for(i=1;i<=lim;i++)
    {
        st1[i]=st1[i-1]+sum;
        sum=sum+b[i];
    }
    
    sum=0;
    for(i=lim;i>0;i--)
    {
        dr1[i]=dr1[i+1]+sum;
        sum=sum+b[i];
    }

    miny=inf;
    for(i=1;i<=lim-dy+1;i++) if(st1[i]+dr[i+dy-1]<miny) miny=st1[i]+dr[i+dx-1];

    g<<miny+min;
    g.close();
      
    
}