Cod sursa(job #439214)

Utilizator tartacutza90Tiberiu Georgescu tartacutza90 Data 11 aprilie 2010 14:10:36
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.08 kb
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int n,u,h;
typedef struct {int val,alt;}gutuie;
gutuie v[100000];
int a[2][100000],maxim;
int f(const void *a,const void *b)
{
  gutuie x,y;
  x=(*(gutuie *)a);
  y=(*(gutuie *)b);
  if(x.alt > y.alt)return -1;
   if(x.alt < y.alt)return 1;
    else 
    {
     if( x.val > y.val)return -1;
       return 1;
    }
}
int max(int a, int b)
{
   if(a>b)return a;
   return b;
}
int main()
{
    fin=fopen("gutui.in","rt");
    fout=fopen("gutui.out","wt");
    fscanf(fin,"%i %i %i",&n,&h,&u);
    for(int i=0;i<n;i++)
     {
      fscanf(fin,"%i %i",&(v[i].alt),&(v[i].val));
      } 
   qsort(v,n,sizeof(gutuie),f);

   int k;
   for(k=0;k<n;k++)
    {
     for(int j=1;j<=n;j++)
      {
        if(v[k].alt+(j-1)*u<=h)a[(k+1)%2][j]=max(a[(k+1)%2][j],a[k%2][j-1]+v[k].val);
        if(a[(k+1)%2][j]>maxim)maxim=a[(k+1)%2][j];
      }
     
    }
  fprintf(fout,"%i",maxim);
  /*  for(int i=0;i<n;i++)
     fprintf(fout,"%i %i\n",v[i].alt,v[i].val);*/
  fclose(fin);
  fclose(fout);
   return 0;
}