Pagini recente » Cod sursa (job #2832367) | Cod sursa (job #2370493) | Cod sursa (job #1781987) | Cod sursa (job #1225452) | Cod sursa (job #435378)
Cod sursa(job #435378)
#include <stdio.h>
#include <stdlib.h>
#define max(a,b) (((a)>(b))?(a):(b))
typedef struct
{
long g;
long h;
long max;
int pred;
int nr;
}nivel;
int cmp(const void* a, const void* b)
{
static int rez;
rez=((nivel*)a)->h-((nivel*)b)->h;
if(rez==0) rez=((nivel*)a)->g-((nivel*)b)->g;
return rez;
}
//nivel v[12];
int main()
{
FILE *fin=fopen("gutui.in", "rt");
FILE *fout=fopen("gutui.out", "wt");
int n, i=1, pi=0, maxp;
long h, u;
nivel *v;
fscanf(fin, "%ld", &n);
++n;
fscanf(fin, "%ld", &h);
++h;
fscanf(fin, "%ld", &u);
maxp=(h-1)/u;
++maxp;
v=(nivel*)calloc(n+1, sizeof(nivel));
v[0].max=0;
v[0].h=-u;
v[0].nr=0;
for(i=1;i<n;++i)
{
fscanf(fin, "%ld%ld", &v[i].h, &v[i].g);
}
qsort(v,n,sizeof(nivel),cmp);
v[n].h=v[n-1].h+2;
--u;
i=1; v[1].pred=0;
while(v[i].h<h && i<n && v[i-1].nr<maxp)
{
v[i].max=max( v[i].g+v[v[i].pred].max , v[i-1].max);
v[i].nr=( (v[i].g+v[v[i].pred].max)> v[i-1].max )? (v[v[i].pred].nr+1) : v[i-1].nr;
pi=v[i].pred;
while (v[pi].h<v[i+1].h)
{
if((v[i+1].h-v[pi].h)>u) v[i+1].pred=pi;
else break;
++pi;
}
//if( v[i+1].h==v[i].h) v[i+1].g+=v[i].g;
++i;
++pi;
};
fprintf(fout, "%ld", v[i-1].max);
free(v);
fclose(fin);
fclose(fout);
return 0;
}