Pagini recente » Cod sursa (job #1710086) | Cod sursa (job #437757)
Cod sursa(job #437757)
#include <iostream>
#include <list>
#include <vector>
using namespace std;
typedef struct
{
long height, weight;
long level;
} Gutuie;
int compare (const void * a, const void * b)
{
Gutuie *g1=(Gutuie *)a;
Gutuie *g2=(Gutuie *)b;
if(((g1->height) - (g2->height))<0)
return -1;
return 1;
}
bool compareH(Gutuie a, Gutuie b)
{
if( (a.height - b.height) < 0 )
return true;
return false;
}
int main()
{
long N, H, U, sum=0;
int i, curent;
Gutuie elem, *g;
//list<Gutuie> gutui;
list<Gutuie>::iterator it,aux;
FILE * in = fopen("gutui.in", "r");
if(in==NULL)
return -1;
fscanf(in, "%ld", &N);
fscanf(in, "%ld", &H);
fscanf(in, "%ld", &U);
// cout<<N<<" "<<H<<" "<<U<<endl;
g=(Gutuie *)malloc(N*sizeof(Gutuie));
for(i=0; i<N; i++)
{
fscanf(in, "%ld", &g[i].height);
fscanf(in, "%ld", &g[i].weight);
g[i].level=(H-g[i].height)/U + 1;
// gutui.push_front(elem);
// cout << "h:" << elem.height << " w:" << elem.weight;
// cout << endl;
}
fclose(in);
qsort (g, N, sizeof(Gutuie), compare);
// for(i=0; i<N; i++)
// cout <<g[i].height <<" "<<g[i].weight<<" "<<g[i].level<<endl;
// cout << endl;
// gutui.sort(compareH);
// for (it=gutui.begin(); it!=gutui.end(); ++it)
// it->level=(H-it->height)/U + 1;
list<Gutuie> gutui (g, g+N);
// cout<<"size: "<<(int)gutui.size()<<endl;
// for (it=gutui.begin(); it!=gutui.end(); ++it)
// cout << "h:" << it->height << " w:" << it->weight<<endl;
cout << endl;
while(!gutui.empty())
{
it=gutui.begin();
curent=it->level;
if(curent==0)
break;
aux=it;
while(curent==it->level)
{
it->level--;
if(aux->weight < it->weight)
{
aux=it;
}
++it;
}
sum+=aux->weight;
aux=gutui.erase(aux);
}
FILE * out = fopen("gutui.out", "w");
fprintf(out,"%ld", sum);
fclose(out);
// int x;
// cin>>x;
return 0;
}