Cod sursa(job #989735)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 26 august 2013 13:22:53
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
#include<string.h>
 
#define DIM 50005
 
FILE *fin=fopen("tribute.in","r");
FILE *fout=fopen("tribute.out","w");
 
int n,dx,dy,ox,oy,maxx,maxy,pozminx,pozminy,i,x,y;
int fx[50010],fy[50010];
long long s[50010];
long long d[50010];
long long suma,min;
 
int main(){
     
    fscanf(fin,"%d %d %d",&n,&dx,&dy);
    dx++;
    dy++;
     
    for(i=1;i<=n;i++){
        fscanf(fin,"%d %d",&x,&y);
         
        fx[x]++;
        fy[y]++;
         
        if(x > maxx){
            maxx = x;
        }
        if(y > maxy){
            maxy = y;
        }
    }
     
    ox=fx[0];
    s[0]=0;
    for(i=1;i<DIM;i++){
        s[i]=s[i-1]+(long long)ox;
        ox+=fx[i];
    }
     
    ox=0;
    d[DIM]=0;
     
    for(i=DIM-2;i>=0;i--){      
        d[i]=d[i+1]+(long long)ox;
        ox+=fx[i];
    }
    min = ((long long)DIM)*DIM;
    for(i=0;i<DIM-dx;i++){
        if(min > s[i] + d[i+dx-1]){
            min = s[i] + d[i+dx-1];
        }
    }
     
    suma+=min;
     
    memset(s,0,sizeof(s));
    memset(d,0,sizeof(d));
     
     
    oy=fy[0];
    for(i=1;i<=DIM-1;i++){      
        s[i]=s[i-1]+(long long)oy;
        oy+=fy[i];
    }
     
    oy=0;  
    for(i=DIM-2;i>=0;i--){
        d[i]=d[i+1]+(long long)oy;
        oy+=fy[i];
    }
    min = ((long long)DIM) * DIM;
    for(i=0;i<DIM-dy;i++){
        if(min > s[i] + d[i+dy-1]){
            min = s[i] + d[i+dy-1];
        }
    }
     
    suma+=min;
 
    fprintf(fout,"%lld",suma);
     
    return 0;
}