Pagini recente » Cod sursa (job #991807) | Cod sursa (job #821523) | Cod sursa (job #1118523) | Cod sursa (job #1705240) | Cod sursa (job #439573)
Cod sursa(job #439573)
#include "stdio.h"
#include "stdlib.h"
typedef struct {
int h,g;
} gutui;
int cmp(void* a, void* b)
{
return ((gutui*)b)->g - ((gutui*)a)->g;
}
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];
for (i=0;i<n;i++)
fscanf(f, "%i %i", &a[i].h, &a[i].g);
qsort(a, n, sizeof(gutui), cmp);
int c[h/u+1];
for (i=0;i<=h/u;i++)
c[i]=0;
unsigned int tot=0;
int contor = 0,j,k;
int boo = 0;
for (j=0;j<n && contor<h/u+1;j++)
{
c[(h-a[j].h)/u]++;//vad daca gutuia curenta poate intra la solutie
for (i=(h-a[j].h)/u,boo=1,k=-1;i<h/u+1 && boo;i++)
{
k+=c[i];
if (k>i) boo = 0;//verific daca dupa ce o adaug la solutie poate fi culeasa
}
if (boo)
{
tot+=a[j].g;
contor++;
}
else
{
c[(h-a[j].h)/u]--;//daca nu
}
}
fprintf(g, "%u", tot);
fclose(f);
fclose(g);
return 0;
}