Pagini recente » Cod sursa (job #1335886) | Cod sursa (job #1605347) | Cod sursa (job #489770) | Cod sursa (job #1589474) | Cod sursa (job #436092)
Cod sursa(job #436092)
#include<stdio.h>
#include<list>
#include<stdlib.h>
using namespace std;
FILE* fin;
FILE* fout;
typedef struct gut{
unsigned int greutate;
unsigned int tmp;
}*gutui;
bool compare_desc(gut first,gut second)
{
if (first.tmp <= second.tmp) return true;
else return false;
}
int main(){
unsigned int** mat;
unsigned int h,u,a,g,maxim;
fin=fopen("gutui.in","r");
fout=fopen("gutui.out","w");
int n,i,j,max;
int t;
list<gut> cos;
list<gut>::iterator it;
fscanf(fin,"%d %d %d\n",&n,&h,&u);
gut *aux;
if(h%u==0)
{
t=0;
max=h/u;
}else
{max=h/u+1;
t=1;
}
for(i=0;i<n;i++)
{
aux=(gut*)malloc(sizeof(struct gut));
fscanf(fin,"%u %u\n",&a,&g);
if(a+(max-t-(a/u))*u<=h)
aux->tmp=max-t-(a/u-1);
else
aux->tmp=max-t-(a/u);
//aux->inaltime=a;
aux->greutate=g;
cos.push_back(*aux);
free(aux);
}
cos.sort(compare_desc);
/* for (it=cos.begin(); it!=cos.end(); ++it)
printf("%u %u\n",it->greutate,it->tmp);
*/
mat=(unsigned int**)malloc(sizeof(unsigned int*)*2);
it=cos.begin();
mat[0]=(unsigned int*)calloc((max+1),sizeof(unsigned int));
mat[1]=(unsigned int*)calloc((max+1),sizeof(unsigned int));
//it=cos.begin();
//printf("%d %d\n",1,it->greutate);
printf("max=%d\n",max);
it=cos.begin();
for(i=1;i<=n;i++)
{
// printf("i=%d tmp=%d\n",i,it->tmp);
/*for(j=0;j<=max;j++)
printf("%d ",mat[0][j]);
printf("\n");
*/
for(j=1;j<=max;j++)
{
mat[0][j]=mat[1][j];
if(j>(int)(it->tmp))
{mat[1][j]=mat[1][it->tmp];
}
else
{
maxim=mat[0][j];
// printf("%d %d\n",j,it->greutate);
if(maxim<mat[0][j-1]+it->greutate)
maxim=mat[0][j-1]+it->greutate;
mat[1][j]=maxim;
}
}
/*for(j=0;j<=max;j++)
printf("%d ",mat[1][j]);
printf("\n\n");
*/
if((int)it->tmp==max)
break;
++it;
}
/*for(i=0;i<=n;i++)
{
for(j=0;j<=max;j++)
printf("%d ",mat[i][j]);
printf("\n");
}
*/
printf("%u\n",mat[1][max]);
fprintf(fout,"%u",mat[1][max]);
/* for(i=0;i<=n;i++)
*/
free(mat[0]);
free(mat[1]);
free(mat);
fclose(fin);
fclose(fout);
return 0;
}