Pagini recente » Cod sursa (job #1388369) | Cod sursa (job #3255431) | Cod sursa (job #2173518) | Cod sursa (job #99161) | Cod sursa (job #438673)
Cod sursa(job #438673)
#include<stdio.h>
#include<stdlib.h>
unsigned long n,m;
double h,u,g=0;
double p[100000][2];
unsigned long nivel[100000];
FILE*f;
void citire(void)
{
unsigned long i;
f=fopen("gutui.in","r");
fscanf(f,"%ld%lf%lf",&n,&h,&u);
for(i=0;i<n;i++)
fscanf(f,"%lf%lf",&p[i][0],&p[i][1]);
fclose(f);
}
void afisare(void)
{
unsigned long i;
printf("%ld %.0f %.0f\n",n,h,u);
for(i=0;i<n;i++)
printf("%.0f %.0f\n",p[i][0],p[i][1]);
}
void sortare()
{
unsigned long i,j,init,aux1,aux2;
double aux;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(p[i][0]<p[j][0])
{
aux=p[i][0];
p[i][0]=p[j][0];
p[j][0]=aux;
aux=p[i][1];
p[i][1]=p[j][1];
p[j][1]=aux;
}
//afisare();
i=0;
m=0;
do
{
init=i;
nivel[m++]=init;
aux1=aux2=p[init][0]/u;
while(i<n&&aux1==aux2)
{
i++;
aux2=p[i][0]/u;
}
for(;init<i-1;init++)
for(j=init+1;j<i;j++)
if(p[init][1]<p[j][1])
{
aux=p[init][0];
p[init][0]=p[j][0];
p[j][0]=aux;
aux=p[init][1];
p[init][1]=p[j][1];
p[j][1]=aux;
}
}while(i<n);
nivel[m]=n;
}
int ajung()
{
unsigned long i;
for(i=0;i<n;i++)
if(h>=p[i][0])
{//printf("gasesc\n");
return 1;}
//printf("nu gasesc\n");
return 0;
}
void culeg()
{
double cmg=0,aux=h;
unsigned long pozitie=-1,i,k=0,j;
aux-=u;
for(i=0;p[i][0]>h;i++);
//getchar();
cmg=p[i][1];
pozitie=i;
k++;
for(j=0;nivel[j]<=i;j++);
i=j;
do
{
aux-=u;
for(;i<m&&p[nivel[i]][0]>aux;i++);
//printf("S-a ales %d si k este%d\n",nivel[i],k);
if(i!=m)
{
if(cmg<p[nivel[i]+k][1]&&nivel[i]+k<nivel[i+1])
{
cmg=p[nivel[i]+k][1];
pozitie=nivel[i]+k;
}
k++;
i++;
}
}while(i!=m);
h-=u;
p[pozitie][0]=h+1;
//printf("culeg pe %u\n",pozitie);
//printf("pot ajunge la inaltimea %f\n",h);
g+=cmg;
}
void la_cules(void)
{
while(ajung())
culeg();
}
int main(void)
{
citire();
//afisare();
sortare();
//afisare();
la_cules();
//printf("am cules %f kg.\n",g);
f=fopen("gutui.out","w");
fprintf(f,"%.0f",g);
fclose(f);
//getchar();
return 0;
}