Pagini recente » Rating Craciun Madalin (Madalin123) | Monitorul de evaluare | Cod sursa (job #437589) | Cod sursa (job #2006848) | Cod sursa (job #439746)
Cod sursa(job #439746)
#include "stdio.h"
typedef struct {
int h,g;
} gutui;
int cmp(void* a, void* b)
{
return ((gutui*)b)->h - ((gutui*)a)->h;
}
int insertArb(int g, int* arb, int n)
{
arb[n]=g;
while ((n-1)/2>=0 && g<arb[(n-1)/2])
{
arb[n] = arb[(n-1)/2];
arb[(n-1)/2] = g;
n = (n-1)/2;
}
return n;
}
int inlocuiesteMin(int g, int *arb, int n)
{
arb[0] = g;
int i=0;
while ((2*i+1<n && g>arb[2*i+1]) || (2*i+2<n && g>arb[2*i+2]))
{
if ((2*i+2<n && arb[2*i+1]<=arb[2*i+2]) || 2*i+2==n)
{
arb[i] = arb[2*i+1];
arb[2*i+1] = g;
i = 2*i+1;
}
else if (2*i+2<n && arb[2*i+1]>arb[2*i+2])
{
arb[i] = arb[2*i+2];
arb[2*i+2] = g;
i = 2*i+2;
}}
return i;
}
int main()
{
FILE *f, *g;
f = fopen("gutui.in", "r");
g = fopen("gutui.out", "w");
int n,i;
int h,u;
fscanf(f, "%i %i %i", &n,&h,&u);
gutui a[n];
int arb[n];
for (i=0;i<n;i++)
fscanf(f, "%i %i", &a[i].h, &a[i].g);
qsort(a, n, sizeof(gutui), cmp);
int nr = 0;
for (i=0;i<n;i++)
if (a[i].h<=h-nr*u)
insertArb(a[i].g, arb, nr++);
else if (a[i].g>arb[0])
inlocuiesteMin(a[i].g, arb, nr);
int tot=0;
for (i=0;i<nr;i++)
tot+=arb[i];
fprintf(g, "%u", tot);
fclose(f);
fclose(g);
return 0;
}