Cod sursa(job #121757)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 9 ianuarie 2008 16:52:17
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>

#define maxn 50010
#define maxx 50000
#define inf 2000000000

int n,minx,miny,dx,dy;
int a[maxn],b[maxn],c[maxn],d[maxn];
int o1[maxn],o2[maxn],v1[maxn],v2[maxn];

int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    
    scanf("%d %d %d ",&n,&dx,&dy);
    
    int i, sum;
    
    for (i=1;i<=n;i++) scanf("%d %d ",&a[i],&b[i]);
    
    for (i=1;i<=n;i++) 
    {
        c[a[i]]++;
        d[b[i]]++;
    }
    
    sum = c[0];
    for (i=1;i<=maxx;i++)    
    {
        o1[i] = o1[i-1] + sum;
        sum += c[i];
    }
    
    sum = 0;
    for (i=maxx;i>=0;i--)
    {
        o2[i] = o2[i+1] + sum;
        sum += c[i];
    }
    
    minx = inf;
    
    for (i=0;i+dx<=maxx;i++)
        if (o1[i] + o2[i+dx] < minx) minx = o1[i] + o2[i+dx];
        
    sum = d[0];
    for (i=1;i<=maxx;i++)    
    {
        v1[i] = v1[i-1] + sum;
        sum += d[i];
    }
    
    sum = 0;
    for (i=maxx;i>=0;i--)
    {
        v2[i] = v2[i+1] + sum;
        sum += d[i];
    }
    
    miny = inf;
    
    for (i=0;i+dy<=maxx;i++)
        if (v1[i] + v2[i+dy] < miny) miny = v1[i] + v2[i+dy];
        
    printf("%d\n",minx + miny);
    
    return 0;
}