Pagini recente » Cod sursa (job #785927) | Cod sursa (job #243723) | Cod sursa (job #2288740) | Cod sursa (job #2820088) | Cod sursa (job #435506)
Cod sursa(job #435506)
#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,&hh,&u);
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;
}
*/
//for(i=0;i<n;i++)
// printf("%ld %ld\n",h[i],g[i]);
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);
fprintf(f2,"%ld",max);
fclose(f1);fclose(f2);
return 0;
}