Pagini recente » Monitorul de evaluare | Cod sursa (job #440860) | Cod sursa (job #2576215) | Cod sursa (job #2195810) | Cod sursa (job #439188)
Cod sursa(job #439188)
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
int n,u,h;
typedef struct {int val,alt;}gutuie;
gutuie v[100000];
int a[2][100000],maxim;
int f(const void *a,const void *b)
{
gutuie x,y;
x=(*(gutuie *)a);
y=(*(gutuie *)b);
if(x.alt > y.alt)return -1;
if(x.alt < y.alt)return 1;
else
{
if( x.val > y.val)return -1;
return 1;
}
}
int max(int a, int b)
{
if(a>b)return a;
return b;
}
int main()
{
fin=fopen("gutui.in","rt");
fout=fopen("gutui.out","wt");
fscanf(fin,"%i %i %i",&n,&h,&u);
for(int i=0;i<n;i++)
{
fscanf(fin,"%i %i",&(v[i].alt),&(v[i].val));
}
qsort(v,n,sizeof(gutuie),f);
int k;
for(k=0;k<n;k++)
{
for(int j=0;j<n;j++)
{
if(v[k].alt+j*u<=h)a[(k+1)%2][j]=max(a[(k+1)%2][j],a[k%2][j-1]+v[k].val);
if(a[(k+1)%2][j]>maxim)maxim=a[(k+1)%2][j];
}
}
fprintf(fout,"%i",maxim);
/* for(int i=0;i<n;i++)
fprintf(fout,"%i %i\n",v[i].alt,v[i].val);*/
fclose(fin);
fclose(fout);
return 0;
}