Cod sursa(job #981788)

Utilizator andrettiAndretti Naiden andretti Data 7 august 2013 22:06:43
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>
#include<algorithm>
#define maxn 100005
using namespace std;

struct sheep_step{int t,val;} a[maxn];
int n,dx,dl,nh,tmax;
int h[maxn];
long long sol;

void read()
{
    int dist,fur,nr;
    scanf("%d%d%d",&n,&dx,&dl);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&dist,&fur);
        nr=0; while(dist<=dx) nr++,dist+=dl;
        a[i].t=nr; a[i].val=fur;
    }
}

int cmp(sheep_step x,sheep_step y) { return x.t>y.t; }

void heap_up(int k)
{
    if(k<=1) return;
    int i=k/2;
    if(h[i]<h[k]) {swap(h[i],h[k]); heap_up(i);}
}

void heap_dw(int k)
{
    int i=2*k;
    if(i<=nh)
    {
        if(i+1<=nh && h[i+1]>h[i]) i++;
        if(h[i]>h[k]) {swap(h[i],h[k]); heap_dw(i);}
    }
}

void extract()
{
    swap(h[1],h[nh--]);
    heap_dw(1);
}

void solve()
{
    int j=1;
    sort(a+1,a+n+1,cmp);
    tmax=a[1].t;
    for(int i=tmax;i>=1;i--)
    {
        for(;a[j].t==i && j<=n;j++) {h[++nh]=a[j].val; heap_up(nh);}
        if(nh>0) sol+=h[1],extract();
    }
}

int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

    read();
    solve();
    printf("%lld",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}