Cod sursa(job #1759013)

Utilizator nnnmmmcioltan alex nnnmmm Data 18 septembrie 2016 13:06:04
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<cstdio>
#include<vector>
#include<algorithm>

const int VAL_MAX=2147483640,NMAX=500001;

///Sume Partiale
int sx[NMAX],sy[NMAX];

int n;

void Update(int &i,int &I,int v[])
{
 while(v[i]-v[i-1]<=I && i<=n)
       i++;
 i--;
}

int Rasp(int l,int v[])
{
 int st=0,dr=l,st_pos=1,dr_pos=1,min=VAL_MAX;
 Update(st_pos,st,v);
 Update(dr_pos,dr,v);
 while(dr_pos<n)
       {
        int a=std::abs(st*st_pos-v[st_pos])+std::abs(dr*(n-dr_pos)-v[n]+v[dr_pos]);
        min=std::min(min,a);
        st++,dr++;
        Update(st_pos,st,v);
        Update(dr_pos,dr,v);
       }
 int a=std::abs(st*st_pos-v[st_pos])+std::abs(dr*(n-dr_pos)-v[n]+v[dr_pos]);
 min=std::min(min,a);
 return min;
}

int main()
{
 FILE *file=fopen("tribute.in","r");
 int dx,dy;
 fscanf(file,"%d %d %d ",&n,&dx,&dy);
 for(int i=1;i<=n;i++)
     {
      fscanf(file,"%d %d ",&sx[i],&sy[i]);
     }
 fclose(file);

 std::sort(sx+1,sx+n+1);
 std::sort(sy+1,sy+n+1);

 for(int i=2;i<=n;i++)
     {
      sx[i]+=sx[i-1];
      sy[i]+=sy[i-1];
     }

 file=fopen("tribute.out","w");
 fprintf(file,"%d\n",Rasp(dx,sx)+Rasp(dy,sy));
 fclose(file);
 return 0;
}