Pagini recente » Cod sursa (job #1220883) | Cod sursa (job #1537063) | Cod sursa (job #1035162) | Cod sursa (job #2858791) | Cod sursa (job #439897)
Cod sursa(job #439897)
#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,aux,s=0,k;
vector<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);
*/
aux = (gutui[n-1].h / u)*u;
aux -=u;
while ((gutui.size() or gutuiDisp.size()) and aux <= h){
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
aux += u;
}
else{
k = (gutui.back().h - aux)/u;
if (k>1)
aux += u*k;
else
aux += u;
}
while (gutui.size() and gutui.back().h <= aux) {
gutuiDisp.push_back(gutui.back().g);
push_heap(gutuiDisp.begin(), gutuiDisp.end()); // refac ordinea de heap
gutui.pop_back(); //scot elementul din lista
}
}
fout = fopen("gutui.out","wt");
fprintf(fout,"%ld",s);
fclose(fin);
fclose(fout);
return 0;
}