#include<stdio.h>
typedef struct element
{
int greutate;
struct element *urm;
}nod;
void afisare(nod *x)
{
if(x==NULL)
{
printf("lista este vida \n");
return;
}
while(x!=NULL)
{
printf("greutatea: %i ",x->greutate);
x = x->urm;
}
printf("\n");
}
void inserare(nod **q,int g)
{
nod *aux,*p,*x;
p=*q;
aux=(nod*)malloc(sizeof(nod));
aux->greutate=g;
aux->urm=NULL;
if(p==NULL)
{
*q=aux;
}
else if(p->greutate<=aux->greutate)
{
aux->urm=p;
*q=aux;
}
else
{
while(p->urm!=NULL && p->urm->greutate>aux->greutate)
{
p=p->urm;
}
aux->urm=p->urm;
p->urm=aux;
}
}
void sterge_prim(nod **q)
{
nod *p;
p=*q;
*q=p->urm;
}
int caut_max(int N,int h[],int g[],int H,int U,int *p)
{
int i;
for(i=0;i<N;i++)
{
if((h[i]<=H+U)&&(h[i]>H)&&(g[i]>0))
{
*p=i;
return g[i];
}
}
return 0;
}
int main()
{
int N,H,U,i,j,x,totalg=0,max,M,*h,*g,**gutui,H_curent=0,index=0;
FILE * pFile = fopen("gutui.in","r");
FILE * dFile = fopen("gutui.out","w");
fscanf(pFile,"%i",&N);
fscanf(pFile,"%i",&H);
fscanf(pFile,"%i",&U);
h=(int*)malloc(N*sizeof(int));
g=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
{
fscanf(pFile,"%i",&h[i]);
fscanf(pFile,"%i",&g[i]);
}
nod *prim = NULL;
M=H/U+(H%U!=0); //numarul de linii in matrice
nod **vector_liste;
vector_liste=(nod**)malloc(M*sizeof(nod*));
for(i=0;i<M;i++)
{
vector_liste[i]=(nod*)malloc(sizeof(nod));
vector_liste[i]->greutate=0;
vector_liste[i]->urm=NULL;
}
i=0;
while(H_curent<=H-U)
{
do
{
max=caut_max(N,h,g,H_curent,U,&x);
if(max)
{
inserare(&vector_liste[i],max);
g[x]=0;
}
}while(max);
H_curent=H_curent+U;
i++;
}
for(i=0;i<M;i++)
{
afisare(vector_liste[i]);
printf("\n");
}
for(i=0;i<M;i++)
{
if((vector_liste[i]->greutate==0)&&(totalg==0))
{
//M--;
continue;
}
if(prim==NULL || vector_liste[i]->greutate>=prim->greutate)
{
//printf("pun o gutuie de greutate: %i\n",vector_liste[i]->greutate);
totalg=totalg+vector_liste[i]->greutate;
vector_liste[i]=vector_liste[i]->urm;
}
else
{
//printf("pun o gutuie de greutate din coada: %i\n",prim->greutate);
totalg=totalg+prim->greutate;
sterge_prim(&prim);
}
while(vector_liste[i] != NULL && vector_liste[i]->greutate!=0)
{
inserare(&prim,vector_liste[i]->greutate);
vector_liste[i]=vector_liste[i]->urm;
}
}
fprintf(dFile,"%i\n",totalg);
printf("total %i\n",totalg);
fclose(pFile);
fclose(dFile);
return 0;
}