Cod sursa(job #437320)

Utilizator mihaela_29Vilceanu Mihaela mihaela_29 Data 9 aprilie 2010 16:41:23
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.7 kb
#include <stdio.h>
#include <iostream.h>
long n,d,hh,g[200000],u,i,h[200000],max,gm[200000],nr_cul[200000],j;
void qsort(long l, long r)                    //ordonez descrescator dupa inaltime
{
     int i,j,x,aux;
     i=l;
     j=r;
     x=h[(l+r)/2];
     do
     {
       while (h[i]>x) i++;
       while (x>h[j]) j--;
       if (i<=j){
          aux=h[i];
          h[i]=h[j];
          h[j]=aux;
          aux=g[i];
          g[i]=g[j];
          g[j]=aux;
          i++;j--;
       }
     }       
     while (i<j);
     if (l<j) qsort(l,j);
     if (i<r) qsort(i,r);
};
int main()
{    int aux;
    FILE *f1=fopen("gutui.in","r");
    FILE *f2=fopen("gutui.out","w");
    fscanf(f1,"%ld%ld%ld\n",&n,&hh,&u);
    for(i=0;i<100000;i++){g[i]=0;h[i]=0;gm[i]=0;nr_cul[i]=0;};
    for(i=0;i<n;i++)
       fscanf(f1,"%ld%ld",&h[i],&g[i]);
    qsort(0,n);
    /*for(i=0;i<n;i++)
       for(j=0;j<i;j++)
          if (h[i]>h[j])
          {
          
          aux=h[i];
          h[i]=h[j];
          h[j]=aux;
          aux=g[i];
          g[i]=g[j];
          g[j]=aux;
          }
       */

    max=0;
    for(i=0;i<n;i++)
    {
       gm[i]=g[i];                    //gm[i]=greutate maxima culeasa incluzand a i-a gutuie
       nr_cul[i]=1;
       for(j=0;j<i;j++)
          if(h[i]+nr_cul[j]*u <= hh && gm[i]<=g[i]+gm[j])//daca inca as putea s-o culeg si daca merita
          {
             gm[i]=gm[j]+g[i];
             nr_cul[i]=nr_cul[j]+1;
          }
       if (gm[i]>max) max=gm[i];
    }
    //printf("%u",max);
    for(i=0;i<n;i++)
       printf("%ld ",gm[i]);system("pause");
    fprintf(f2,"%ld",max);
    fclose(f1);fclose(f2);
    return 0;    
}