Pagini recente » Cod sursa (job #1156699) | Cod sursa (job #1618394) | Cod sursa (job #613703) | Cod sursa (job #1598684) | Cod sursa (job #434699)
Cod sursa(job #434699)
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#include<sys/types.h>
using namespace std;
#define height first
#define weight second
#define poh pop_heap
#define pob pop_back
#define pub push_back
#define puh 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() {
uint32_t n,h,u,i,j,k;
uint64_t sum = 0;
ifstream f("gutui.in",ios::in);
ofstream g("gutui.out",ios::out);
vector<pair<uint32_t,uint32_t> > x, aux;
f>>n>>h>>u;
for(i=0;i<n;i++) {
f>>j>>k;
x.push_back(make_pair(j,k));
}
sort(x.begin(),x.end(),sortHeight);
aux.push_back(x[0]);
make_heap(aux.begin(),aux.end(),sortWeight);
for(i=1;i<n;i++) {
if(aux.size()==(1+(h-x[i].height)/u) && aux.front().weight<x[i].weight) {
poh(aux.begin(),aux.end(),sortWeight);
aux.pob();
aux.pub(make_pair(x[i].height,x[i].weight));
puh(aux.begin(),aux.end(),sortWeight);
}
else if(aux.size()!=(1+(h-x[i].height)/u))
{
aux.pub(make_pair(x[i].height,x[i].weight));
puh(aux.begin(),aux.end(),sortWeight);
}
}
for (i=0; i<aux.size(); i++)
sum+=aux[i].weight;
g<<sum;
return 0;
}