Pagini recente » Cod sursa (job #1264893) | Cod sursa (job #766678) | Cod sursa (job #3124249) | Cod sursa (job #656412) | Cod sursa (job #437058)
Cod sursa(job #437058)
#include<stdio.h>
#include<list>
#include<stdlib.h>
#include<algorithm>
#include<vector>
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
if(first.tmp == second.tmp)
{ if(first.greutate<=second.greutate)
return true;
else
return false;
}
return false;
}
int main(){
unsigned int h,u,a,g,maxim;
fin=fopen("gutui.in","r");
fout=fopen("gutui.out","w");
unsigned 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);
unsigned int *matrice;
matrice=(unsigned int*)calloc(max+1,sizeof(unsigned int));
printf("max=%d\n",max);
int suma=0;
int timp=n;
int ind=0;
unsigned int top,poz,full=0;
unsigned int min;
unsigned int pozMin=0;
it=cos.begin();
ind=it->tmp;
poz=it->tmp;
top=it->tmp;
unsigned int v[]={};
vector<unsigned int> luate(v,v+6);
/* printf("heapuri\n");
make_heap(luate.begin(),luate.end());
for(i=0;i<luate.size();i++)
printf("%d ",luate[i]);
printf("\n");
pop_heap(luate.begin(),luate.end());
luate.pop_back();
for(i=0;i<luate.size();i++)
printf("%d ",luate[i]);
printf("\n");
luate.push_back(12);
push_heap(luate.begin(),luate.end());
luate.push_back(32);
push_heap(luate.begin(),luate.end());
luate.push_back(22);
push_heap(luate.begin(),luate.end());
for(i=0;i<luate.size();i++)
printf("%d ",luate[i]);
printf("\n");
*/
unsigned int nivel;
for(i=1;i<=n;i++)
{
if(i<=it->tmp){
suma=suma+it->greutate;
luate.push_back(it->greutate);
push_heap(luate.begin(),luate.end());
}
else
{if(luate.front()<it->greutate)
suma=suma-luate.front()+it->greutate;
pop_heap(luate.begin(),luate.end());
luate.pop_back();
luate.push_back(it->greutate);
push_heap(luate.begin(),luate.end());
}
it++;
}
/* printf("\n");
for(i=1;i<=top;i++)
printf("%d ",i);
printf("\n");
for(i=1;i<=top;i++)
printf("%d ",matrice[i]);
printf("\n");
*/
printf("%u\n",suma);
fprintf(fout,"%u",suma);
free(matrice);
fclose(fin);
fclose(fout);
return 0;
}