Cod sursa(job #439682)

Utilizator AngelloAndrei Pricop Angello Data 11 aprilie 2010 18:20:05
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 1.72 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct 
{
        long inaltime,greutate;
}fruct;

long N,H,U,G,min;
fruct *gutui;

void citire()
{
     int i;
     FILE *f=fopen("gutui.in","rt");
     if(!f)
     {
           printf("File not found!");
           return;
     }
     fscanf(f,"%li%li%li",&N,&H,&U);
     gutui=(fruct*)calloc(N,sizeof(fruct));

     if(!gutui)
     {
               printf("Alocare esuata.");
               return;
     }  
     for(i=0;i<N;i++)
          fscanf(f,"%li%li",&gutui[i].inaltime,&gutui[i].greutate);
     fclose(f);
     return;
}
     
int sort_function(const void *a,const void *b)
{
    fruct *A=(fruct*)a;
    fruct *B=(fruct*)b;
    return B->greutate - A->greutate;
}

void solve()
{
     int i,j,k;
     long n;
     long Imin,Nmax,Gmax=0;
     Imin=gutui[0].inaltime;
     for(i=1;i<N;i++)
                     if (gutui[i].inaltime<Imin) Imin=gutui[i].inaltime;
     Nmax=(H-Imin)/U;
     Nmax++;
     qsort((void*)gutui,N,sizeof(fruct),sort_function);
     long L[Nmax];
     for(i=0;i<Nmax;i++)
                        L[i]=i+1;
     n=Nmax;
     k=0;
     while ((Nmax!=0)&&(k<N))
			{
				
				j=(H-gutui[k].inaltime)/U;
				if (L[j]>0)
				{
					Gmax=Gmax+gutui[k].greutate;
					for(i=n-1;(i>=j)&&(L[i]!=0);i--)
						L[i]--;
					
					Imin=L[i+1];
					for(;(i>=0)&&(L[i]!=0);i--)
						if(L[i]>Imin) L[i]=Imin;
					Nmax--;
				}
				k++;
			}
      FILE *f=fopen("gutui.out","wt");
      if(!f)
      {
           printf("File not found!");
           return;
      }
      fprintf(f,"%li",Gmax);
      fclose(f);
      return;
     
}
    

int main()
{
     citire();
     solve();
     return 1;
}