Cod sursa(job #882176)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 18 februarie 2013 22:15:59
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.32 kb
#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;
}