Cod sursa(job #1657923)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 20 martie 2016 21:33:23
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>
#define MAXN 50000
using namespace std;
int x[MAXN],y[MAXN],x1[MAXN],y1[MAXN],ssm1[MAXN+1],ssm2[MAXN+1],vfx[MAXN+1],vfy[MAXN+1];
int n;
inline int myabs(int x){
     if(x<0) return -x;
     return x;
}
inline int getmin(int a,int b){
      if(a>b) return b;
      return a;
}
inline int cauta(int st,int dr,int *v){
      int s=0;
      for(int i=0;i<n;i++)
        if(st>v[i]||v[i]>dr)
              s=s+getmin(myabs(v[i]-st),myabs(v[i]-dr));
      return s;
}
int main(){
    FILE*fi,*fout;
    int dx,dy,i,minx,miny,xm,ym,s;
    fi=fopen("tribute.in" ,"r");
    fout=fopen("tribute.out" ,"w");
    fscanf(fi,"%d%d%d" ,&n,&dx,&dy);
    for(i=0;i<n;i++){
        fscanf(fi,"%d%d" ,&x[i],&y[i]);
        x1[i]=x[i];
        y1[i]=y[i];
        vfx[x[i]]++;
        vfy[y[i]]++;
    }
    sort(x1,x1+n);
    sort(y1,y1+n);
    xm=x1[(n-1)/2];
    ym=y1[(n-1)/2];
    for(i=0;i<=MAXN;i++)
         if(i==0)
            ssm1[i]=vfx[i];
         else
            ssm1[i]=ssm1[i-1]+vfx[i];
    for(i=MAXN;i>=0;i--)
         if(i==MAXN)
             ssm2[i]=vfx[i];
         else
             ssm2[i]=ssm2[i+1]+vfx[i];
    minx=s=cauta(0,dx,x);
    for(i=dx+1;i<=xm+dx;i++){
        s=s+ssm1[i-dx-1]-ssm2[i];
        if(minx>s)
           minx=s;
    }
    for(i=0;i<=MAXN;i++)
         if(i==0)
            ssm1[i]=vfy[i];
         else
            ssm1[i]=ssm1[i-1]+vfy[i];
    for(i=MAXN;i>=0;i--)
         if(i==MAXN)
             ssm2[i]=vfy[i];
         else
             ssm2[i]=ssm2[i+1]+vfy[i];
    miny=s=cauta(0,dy,y);
    for(i=dy+1;i<=ym+dy;i++){
        s=s+ssm1[i-dy-1]-ssm2[i];
        if(miny>s)
           miny=s;
    }
    fprintf(fout,"%d" ,minx+miny);
    fclose(fi);
    fclose(fout);
    return 0;
}