Mai intai trebuie sa te autentifici.
Cod sursa(job #439831)
Utilizator | Data | 11 aprilie 2010 19:39:52 | |
---|---|---|---|
Problema | Gutui | Scor | 100 |
Compilator | c | Status | done |
Runda | teme_upb | Marime | 1.08 kb |
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
long g;
long h;
long nr;
}nivel;
int cmp(const void* a, const void* b)
{
static long rez;
rez=((nivel*)b)->g-((nivel*)a)->g;
if(rez==0) rez=((nivel*)a)->h-((nivel*)b)->h;
return rez;
}
int main()
{
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
int n, i;
long h, u, nivmax, nniv=0, max=0, j;
nivel *v;
long *rez;
fscanf(fin,"%d%ld%ld", &n, &h, &u);
nivmax=h/u+1;
v=(nivel*)calloc(n, sizeof(nivel));
rez=(long*)calloc(nivmax, sizeof(long));
for(i=0;i<n;++i)
{
fscanf(fin,"%ld%ld", &v[i].h, &v[i].g);
v[i].nr=(h-v[i].h)/u;
if(v[i].h==0) v[i].nr=nivmax-1;
if( v[i].h>h || v[i].g<1 ) {--i; --n;}
}
for(i=0;i<nivmax;++i) { rez[i]=i; }
qsort(v,n,sizeof(nivel),cmp);
i=0;
while( nniv<nivmax && i<n )
{
j=rez[v[i].nr];
while(j>-1)
{
if(rez[j]==j) { max+=v[i].g; ++nniv; --rez[j]; break; }
if(j!=v[i].nr) --rez[j];
j=--rez[v[i].nr];
}
++i;
};
fprintf(fout,"%ld", max);
fclose(fin);
fclose(fout);
return 0;
}