Cod sursa(job #439682)
#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;
}