Pagini recente » Cod sursa (job #2928995) | Cod sursa (job #1934494) | Cod sursa (job #871755) | Cod sursa (job #842341) | Cod sursa (job #440182)
Cod sursa(job #440182)
#include <iostream>
#include <vector>
#include <list>
using namespace std;
struct Gutuie{
long int h,g;
};
int comparaGutui(Gutuie g1,Gutuie g2){
return g1.h > g2.h;
}
int main(){
FILE *fin,*fout;
long int n,h,u,i,nivel,s=0,k;
vector<long int> gutuiDisp;
fin = fopen("gutui.in","rw");
fscanf(fin,"%ld %ld %ld",&n,&h,&u);
vector<Gutuie> gutui(n);
for (i=0;i<n;i++){
fscanf(fin,"%ld %ld",&(gutui[i].h),&(gutui[i].g));
}
sort(gutui.begin(),gutui.end(),comparaGutui);
/*for (i=0;i<n;i++)
printf("%ld %ld\n",gutui[i].h,gutui[i].g);
*/
nivel = (gutui.back().h / u)*u;
while ((gutui.size() or gutuiDisp.size()) and nivel <= h){
//actualizare vector (heap) de gutui disponibile
while (gutui.size() and gutui.back().h <= nivel) {
gutuiDisp.push_back(gutui.back().g);
push_heap(gutuiDisp.begin(), gutuiDisp.end()); // refac ordinea de heap
gutui.pop_back(); //scot elementul din lista
}
/*printf("\nnivel = %ld \n",nivel);
vector<long int>::const_iterator it;
for (it=gutuiDisp.begin();it!=gutuiDisp.end();++it)
printf("%ld ",*it);
*/
if (gutuiDisp.size()){
s += gutuiDisp.front();
pop_heap(gutuiDisp.begin(),gutuiDisp.end()); // rearanjeaza heapul - cea mai mare greutate este ultima
gutuiDisp.pop_back(); // scot greutatea
nivel += u;
}
else{
k = (gutui.back().h - nivel)/u;
if (k>1)
nivel += u*k;
else
nivel += u;
}
/*printf("\n");
for (it=gutuiDisp.begin();it!=gutuiDisp.end();++it)
printf("%ld ",*it);*/
}
fout = fopen("gutui.out","wt");
fprintf(fout,"%ld",s);
fclose(fin);
printf("%ld",s);
fclose(fout);
return 0;
}