Pagini recente » Cod sursa (job #454168) | Cod sursa (job #2951624) | Cod sursa (job #2079312) | Cod sursa (job #2102747) | Cod sursa (job #440173)
Cod sursa(job #440173)
#include<stdlib.h>
#include<stdio.h>
long partition(long v[2][100000],long left,long right,long index)
{
long pivotValue=v[0][index];
long aux,i;
aux=v[0][right];
v[0][right]=v[0][index];
v[0][index]=aux;
aux=v[1][right];
v[1][right]=v[1][index];
v[1][index]=aux;
long storeIndex=left;
for (i=left;i<right;i++)
if (v[0][i]>pivotValue)
{
aux=v[0][i];
v[0][i]=v[0][storeIndex];
v[0][storeIndex]=aux;
aux=v[1][i];
v[1][i]=v[1][storeIndex];
v[1][storeIndex]=aux;
storeIndex++;
}
aux=v[0][storeIndex];
v[0][storeIndex]=v[0][right];
v[0][right]=aux;
aux=v[1][storeIndex];
v[1][storeIndex]=v[1][right];
v[1][right]=aux;
return storeIndex;
}
void quicksort(long v[2][100000],long left,long right)
{
long pivot,pivotNew;
if (left<right)
{
pivot=(left+right)/2;
pivotNew=partition(v,left,right,pivot);
quicksort(v,left,pivotNew-1);
quicksort(v,pivotNew+1,right);
}
}
int main()
{
FILE *f,*o;
f=fopen("gutui.in","r");
o=fopen("gutui.out","w");
long N,H,U;
fscanf(f,"%li",&N);
fscanf(f,"%li",&H);
fscanf(f,"%li",&U);
long i=0,g,h;
long v[2][100000],sol[100000];
while (fscanf(f,"%li%li",&h,&g)!=EOF)
{
v[0][i]=h;
v[1][i]=g;
i++;
}
quicksort(v,0,N-1);
//for (i=0;i<N;i++)
//fprintf(o,"%i %i\n",v[0][i],v[1][i]);
long H2=H,k=0,min,j,poz;
for (i=0;i<N;i++)
{
if (v[0][i]<=H2)
{
sol[k]=v[1][i];
k++;
H2=H2-U;
}
else
{
min=sol[0];
for (j=0;j<k;j++)
if (sol[j]<min)
{
min=sol[j];
poz=j;
}
if (v[1][i]>min)
sol[poz]=v[1][i];
}
}
long sum=0;
for (j=0;j<k;j++)
sum=sum+sol[j];
fprintf(o,"%li\n",sum);
fclose(f);
fclose(o);
return 0;
}