Pagini recente » Cod sursa (job #1689021) | Cod sursa (job #1091589) | Cod sursa (job #2380582) | Cod sursa (job #321291) | Cod sursa (job #442550)
Cod sursa(job #442550)
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//#include<conio.h>
typedef struct {long i; long g;} Gutui;
long n, h, u, i;
long compare (const void * b, const void * a)
{
long r;
if ((h-(*(Gutui*)b).i)/u!=(h-(*(Gutui*)a).i)/u)
r=((Gutui*)a)->i - (*(Gutui*)b).i;
else
r=((Gutui*)a)->g - (*(Gutui*)b).g;
if (r>0) return 1;
else if (r<0) return -1;
return 0;
}
int main(){
Gutui *g;
long *c, picks=1, j;
FILE *f,*f2;
f=fopen("gutui.in","rt");
f2=fopen("gutui.out","wt");
fscanf(f,"%li",&n);
fscanf(f,"%li",&h);
fscanf(f,"%li",&u);
g = (Gutui*)malloc(n*sizeof(Gutui));
if (n<h/u)
c=(long*)malloc(n*sizeof(long));
else
c=(long*)malloc((h/u+1)*sizeof(long));
for (i=0;i<n;i++){
fscanf(f,"%li",&g[i].i);
fscanf(f,"%li",&g[i].g);
}
qsort (g, n, sizeof(Gutui), compare);
c[0]=g[0].g;
for (i=1;i<n;i++)
if ((h-g[i].i)/u>=picks){
if (c[picks-1]<g[i].g){
for (j=picks-1;j>=0;j--)
if (c[j]<g[i].g)
c[j+1]=c[j];
else
break;
j++;
c[j]=g[i].g;
picks++;
}
else
c[picks++]=g[i].g;
}
else if ((h-g[i].i)/u>=picks-1){
if (c[picks-1]<g[i].g)
if (c[picks-2]<g[i].g){
for (j=picks-2;j>=0;j--)
if (c[j]<g[i].g)
c[j+1]=c[j];
else
break;
j++;
c[j]=g[i].g;
}
else
c[picks-1]=g[i].g;
}
/*
for (i=0;i<n;i++)
printf("%i ",g[i].i);
printf("\n");
for (i=0;i<n;i++)
printf("%i ",g[i].g);
printf("\n");
for (i=0;i<picks;i++)
printf("%i ",c[i]);
printf("\n%i ",picks);
*/
j=0;
for (i=0;i<picks;i++)
j+=c[i];
fprintf(f2,"%li",j);
// getch();
return 0;
}