Pagini recente » Cod sursa (job #2448584) | Cod sursa (job #2258493) | Cod sursa (job #2755935) | Cod sursa (job #2074823) | Cod sursa (job #882176)
Cod sursa(job #882176)
#include<cstdio>
#include<algorithm>
using namespace std;
#define NM 100001
int N,H,U,cost,nh;
int h[NM],ind[NM],timp[NM],profit[NM];
bool cmp(const int &i, const int &j) {
if (timp[i]>timp[j]) {
return true;
}
return false;
}
void urca(int k) {
int key = h[k];
while (k-1 && key>h[k>>1]) {
h[k]=h[k>>1];
k>>=1;
}
h[k]=key;
}
void coboara(int k) {
if ( (k<<1) > nh) {
return;
}
int fiu=k;
if (h[k]<h[k<<1]) {
fiu=(k<<1);
}
if ((k<<1)+1<=nh && h[fiu]<h[(k<<1)+1]) {
fiu=(k<<1)+1;
}
if (fiu == k) {
return;
}
int aux = h[fiu];
h[fiu] = h[k];
h[k] =aux;
k=fiu;
coboara(fiu);
}
void add(int x) {
h[++nh]=x;
urca(nh);
}
int main() {
freopen("gutui.in","r",stdin);
freopen("gutui.out","w",stdout);
scanf("%d %d %d",&N,&H,&U);
for (int i=1; i<=N; ++i) {
int h;
scanf("%d %d",&h,&profit[i]);
timp[i]=(H-h)/U;
ind[i]=i;
}
sort(ind+1,ind+1+N,cmp);
int j=1;
for (int i=timp[ind[1]]; i>=0; --i) {
while (timp[ind[j]] == i && j<=N) {
add(profit[ind[j]]);
++j;
}
if (nh) {
cost+=h[1];
h[1]=h[nh--];
coboara(1);
}
}
printf("%d\n",cost);
return 0;
}