Pagini recente » Rating Pislariu Mario (pierdcasa) | Cod sursa (job #3041438) | Cod sursa (job #1670664) | Cod sursa (job #2133608) | Cod sursa (job #440764)
Cod sursa(job #440764)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Gutuie{
long int h,g,ls;
};
int comparaGutui(Gutuie g1,Gutuie g2){
return g1.h > g2.h;
}
int main(){
FILE *fin,*fout;
long int n,h,u,i,nivel,gMax=0;
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));
gutui[i].ls = (h-gutui[i].h)/u; //stabilire life-span
}
sort(gutui.begin(),gutui.end(),comparaGutui);
nivel = gutui[n-1].ls;
while ((gutui.size() or gutuiDisp.size()) and nivel != -1){
//actualizare vector (heap) de gutui disponibile
while (gutui.size() and gutui.back().ls == nivel) {
gutuiDisp.push_back(gutui.back().g);
push_heap(gutuiDisp.begin(), gutuiDisp.end()); // refac ordinea de heap
gutui.pop_back(); //scot elementul din lista
}
nivel --;
if (gutuiDisp.size()){
gMax += gutuiDisp.front();
pop_heap(gutuiDisp.begin(),gutuiDisp.end()); // rearanjeaza heapul - cea mai mare greutate este ultima
gutuiDisp.pop_back(); // scot greutatea
}
}
fout = fopen("gutui.out","wt");
fprintf(fout,"%ld",gMax);
fclose(fin);
fclose(fout);
return 0;
}