Cod sursa(job #331290)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 13 iulie 2009 15:30:20
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream.h>
#include<algorithm>

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

const int maxn=100005;

int h[maxn],n,i,j,x,l,maxt,p;

long long s;

struct nod
{
    int d;
    int l;
}
a[maxn];

bool fcomp(nod a,nod b)
{
    return a.d<b.d;
}

void push(int x)
{
    int aux;
    while(x>1&&(x>>1)&&h[x>>1]<h[x])
    {
        aux=h[x];
        h[x]=h[x>>1];
        h[x>>1]=aux;
        x>>=1;
    }
}

void pop(int x)
{
    int aux,y=0;
    while(x!=y)
    {
        y=x;
        if((y<<1)<=p&&h[y<<1]>h[y])
            x=y<<1;
        if((y<<1)+1<=p&&h[(y<<1)+1]>h[x])
            x=(y<<1)+1;
        aux=h[x];
        h[x]=h[y];
        h[y]=aux;
    }
}

int main()
{
    f>>n>>x>>l;
    maxt=-0x3f3f3f3f;
    for(i=1;i<=n;++i)
        f>>a[i].d>>a[i].l,a[i].d=(x-a[i].d)/l+1,maxt=max(maxt,a[i].d);
    sort(a+1,a+n+1,fcomp);

    int pos = n;
	for(int i = maxt; i >= 1; i--)
	{
		while(a[pos].d == i)
		{
			h[++p] = a[pos].l;
			push(p);
			pos--;
		}
		if(p)
		{
			s+= h[1];
			h[1] = h[p];
			h[p--]=0;
			pop(1);
		}
	}
    g<<s<<"\n";
    f.close();
    g.close();

    return 0;
}