Pagini recente » Cod sursa (job #2417099) | Cod sursa (job #440504)
Cod sursa(job #440504)
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<sys/types.h>
using namespace std;
#define height first
#define weight second
#define pb push_back
#define ph push_heap
bool sortWeight(pair<uint32_t,uint32_t>i,pair<uint32_t,uint32_t>j) {
return(i.weight>j.weight);
}
bool sortHeight(pair<uint32_t,uint32_t>i,pair<uint32_t,uint32_t>j) {
return(i.height>j.height);
}
int main() {
// Declarari
uint32_t n,h,u,i,j,k;
uint64_t sum = 0;
ifstream f("gutui.in",ios::in);
ofstream g("gutui.out",ios::out);
// Datele de intrare
vector<pair<uint32_t,uint32_t> > x;
// Heapul auxiliar
vector<pair<uint32_t,uint32_t> > aux;
// Citiri
f>>n>>h>>u;
for(i=0;i<n;i++) {
f>>j>>k;
x.push_back(make_pair(j,k));
}
// Ordonare descrescator dupa inaltimi
sort(x.begin(),x.end(),sortHeight);
// In heap tinem minte initial cea mai inalta gutuie
aux.push_back(x[0]);
// Pentru fiecare gutuie, de la cea mai inalta la cea mai joasa
for(i=1;i<n;i++) {
// Daca heapul e plin, dar putem imbunatati suma:
if(aux.size()==(1+(h-x[i].height)/u) && aux.front().weight<x[i].weight) {
// Facem schimb intre cea mai usoara gutuie din heap si gutuia curenta
pop_heap(aux.begin(),aux.end(),sortWeight);
aux.pop_back();
aux.pb(make_pair(x[i].height,x[i].weight));
ph(aux.begin(),aux.end(),sortWeight);
}
// Daca heapul nu e plin inseram gutuia curenta
else if(aux.size()!=(1+(h-x[i].height)/u))
{
aux.pb(make_pair(x[i].height,x[i].weight));
ph(aux.begin(),aux.end(),sortWeight);
}
}
// Raspunsul este suma greutatilor gutuilor din heap
for (i=0; i<aux.size(); i++)
sum+=aux[i].weight;
g<<sum;
return 0;
}