Pagini recente » Cod sursa (job #1588929) | Cod sursa (job #2938752) | Cod sursa (job #1241053) | Cod sursa (job #2506479) | Cod sursa (job #436766)
Cod sursa(job #436766)
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
struct gutuie{
int h,w;
};
// folosit pt priority_queue
bool operator < (const gutuie &x, const gutuie &y){
return x.w>y.w;
}
bool sortcmp_h (gutuie x, gutuie y){
return x.h>y.h;
}
int main (){
int n,h,u,i;
int gathered=0;
gutuie g[100000];
priority_queue<gutuie> taken;
freopen("gutui.in","rt",stdin);
freopen("gutui.out","wt",stdout);
scanf("%d %d %d",&n,&h,&u);
// .h e folosit ca numar de pasi maxim dupa care se poate culege gutuia, nu ca inaltime efectiva
for (i=0; i<n; i++){
scanf("%d %d",&g[i].h, &g[i].w);
g[i].h=((h-g[i].h)/u)+1;
}
sort(g, g+n, sortcmp_h);
//gutuie tmp;
int tmp_w;
for (i=0; i<n; i++){
if (g[i].h >= i){
taken.push(g[i]);
gathered += g[i].w;
} else {
tmp_w = taken.top().w;
if (!taken.empty() && g[i].w > tmp_w){
gathered -= tmp_w;
gathered += g[i].w;
taken.pop();
taken.push(g[i]);
}
}
}
printf("%d\n",gathered);
return 0;
}