Cod sursa(job #1317990)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 15 ianuarie 2015 14:44:12
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.34 kb
/***/

#include<stdio.h>
#include<algorithm>
using namespace std;
struct oi{
    int d,a;
}nr[100010];
long long sum;
int hn,heap[100010];
pair <int,int> v[100010];
void schimb(int i,int poz){
    int aux=heap[poz];
    heap[poz]=heap[i];
    heap[i]=aux;
}
void upheap(int i){
    int poz=i>>1;
    if(heap[i]>heap[poz] && poz>0){
        schimb(i,poz);
        upheap(poz);
    }
}
void downheap(int i){
    int st=i<<1,max;
    max=i;
    if(st<=hn && heap[max]<heap[st])
        max=st;
    ++st;
    if(st<=hn && heap[max]<heap[st])
        max=st;
    if(max!=i){
        schimb(i,max);
        downheap(max);
    }
}
int main(){
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    int n,x,l,i,tmax;
    scanf("%d%d%d",&n,&x,&l);
    for(i=0;i<n;++i){
        scanf("%d%d",&nr[i].d,&nr[i].a);
        v[i].second=i;
        v[i].first=(x-nr[i].d)/l;
    }
     
    sort(v,v+n);
    tmax=v[n-1].first;
    hn=0;
    i=n-1;
    while(i>=0 && tmax>=0){
        while(tmax==v[i].first && i>=0){
            heap[++hn]=nr[v[i].second].a;
            upheap(hn);
            --i;
        }
        if(hn>0){
            sum+=(long long)heap[1];
            heap[1]=heap[hn--];
            heap[hn+1]=0;
            downheap(1);
        }
        --tmax;
    }
    printf("%lld\n",sum);
     
    fclose(stdin);
    fclose(stdout);
    return 0;
}