Pagini recente » Cod sursa (job #580693) | Cod sursa (job #1189579) | Cod sursa (job #2575004) | Cod sursa (job #757426) | Cod sursa (job #437320)
Cod sursa(job #437320)
#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;
}