Cod sursa(job #492488)

Utilizator cristian9Cristian Zloteanu cristian9 Data 14 octombrie 2010 18:38:17
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<stdio.h>

int f1[50001], f2[50001];

int main(){
    freopen ("tribute.in", "r", stdin);
    freopen ("tribute.out", "w", stdout);

    int n, dx, dy, i, x, y, max1=0, max2=0, min1=50000, min2=50000, smin1, smin2, s1=0,s2=0,p2=0,p1=0;

    scanf("%d %d %d ", &n, &dx, &dy);

    for(i=1; i<=n; i++){
        scanf("%d %d ", &x, &y);
        if(x>max1)
            max1=x;
        if(x<min1)
            min1=x;
        if(y>max2)
            max2=y;
        if(y<min2)
            min2=y;
        f1[x]++; f2[y]++;
    }

    for(i=min1+1+dx; i<=max1; i++)
        if(f1[i]){
            p1+=f1[i];
            s1+=f1[i]*(i-min1-dx);
        }

    smin1=s1;
    for(i=min1+1; i<=max1-dx; i++){
        s2+=p2;
        p2+=f1[i-1];
        s2+=f1[i-1];
        s1-=p1;
        p1-=f1[i+dx];
        if (s1+s2 < smin1)
            smin1=s1+s2;
    }

    p1=0; s1=0;
    for(i=min2+1+dy; i<=max2; i++)
        if(f2[i]){
            p1+=f2[i];
            s1+=f2[i]*(i-min2-dy);
        }

    smin2=s1;
    s2=0;p2=0;
    for(i=min2+1; i<=max2-dy; i++){
        s2+=p2;
        p2+=f2[i-1];
        s2+=f1[i-1];
        s1-=p1;
        p1-=f1[i+dy];
        if(s1+s2 < smin2)
            smin2=s1+s2;
    }

    printf("%d ", smin1+smin2);

    return 0;
}