Pagini recente » Cod sursa (job #1983315) | Cod sursa (job #3211754) | Cod sursa (job #2079956) | Cod sursa (job #442183) | Cod sursa (job #437629)
Cod sursa(job #437629)
#include "stdio.h"
int h,u;
typedef struct {
int h,g;
int val;
} gutui;
int cmp(void* a, void* b)
{
int x = (((gutui*)b)->h)/u - (((gutui*)a)->h)/u;
return (x?x:(((gutui*)b)->g - ((gutui*)a)->g));
}
int cmp2(void* a, void* b)
{
int x = ((gutui*)b)->g - ((gutui*)a)->g;
//return (x?x:((gutui*)b)->val - ((gutui*)a)->val);
return x;
}
int main()
{
FILE *f, *g;
f = fopen("gutui.in", "r");
g = fopen("gutui.out", "w");
int n,i;
fscanf(f, "%i %i %i", &n,&h,&u);
gutui a[n];
gutui b[n];
for (i=0;i<n;i++)
{
fscanf(f, "%i %i", &a[i].h, &a[i].g);
a[i].val = 0;
}
qsort(a, n, sizeof(gutui), cmp2);
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;
int indice;
for (j=0;j<n && contor<h/u+1;j++)
{
indice = (h-a[j].h)/u;
c[indice]++;//vad daca gutuia curenta poate intra la solutie
for (i=0,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;
printf("%i %i\n", a[j].h, a[j].g);
contor++;
}
else
{
c[indice]--;//daca nu
}
}
fprintf(g, "%u", tot);
printf("%u\n", tot);
close(f);
close(g);
return 0;
}