Cod sursa(job #824697)

Utilizator LuffyBanu Lavinia Luffy Data 26 noiembrie 2012 21:10:20
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#define dim 100005

using namespace std;

FILE *f=fopen("lupu.in","r"), *g=fopen("lupu.out","w");

int i,n,x,l,d,a,max,man;
int v[dim],puf[dim];
long long Sumpuf;


void qsort(int prim, int ultim)
{int i,j,temp;

 i = prim; j = ultim; temp = v[(i+j)/2];

 do
 {
    while(v[i] < temp) i++;
    while(v[j] > temp) j--;

    if(i<j) {a=v[i]; v[i]=v[j]; v[j]=a;
             a=puf[i]; puf[i]=puf[j]; puf[j]=a; }

    if(i<=j) {i++; j--;}
 }while(i<=j);

 if(i<ultim) qsort(i,ultim);
 if(prim<j) qsort(prim,j);

}



int main()
{

  fscanf(f,"%d%d%d",&n,&x,&l);
  for(i=1; i<=n; i++)
 {fscanf(f,"%d%d",&d,&a);
   man = (x-d)/l+1; // pasul maxim la care poate fi mancata oaia i
   v[i] = man;
   puf[i] = a;
 }

 qsort(1,n);

 //construirea heapului dupa timpii din v si alegerea maximului de pufosenie
 max = puf[1];
 for(i=2; i<=n+1; i++)
  if(v[i] != v[i-1]) {Sumpuf += max; max = puf[i];}
  else
    if(puf[i] > max) max = puf[i];

 fprintf(g,"%lld\n",Sumpuf);

 return 0;
}