Cod sursa(job #806159)

Utilizator andreinsAndrei Nae andreins Data 1 noiembrie 2012 22:16:04
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<algorithm>
using namespace std;
long long nh, h[100001];
ifstream in("lupu.in");
ofstream out("lupu.out");

void schimb(long long &a, long long &b)
{
	long long pahar=a;
	a=b;
	b=pahar;
}

void urca(long long p)
{
    if(p==1 || h[p]>=h[p/2])
        return;
    schimb(h[p],h[p/2]);
    urca(p/2);
}

struct oaie
{
	long long km;
	long long kg;
}oi[100001];

void coboara(long long p)
{
    long long fs=2*p,fd=2*p+1,t=p;
    if(fs<=nh && h[fs]<=h[t])
        t=fs;
    if(fd<=nh && h[fd]<=h[t])
        t=fd;
    if(t!=p){
        schimb(h[p],h[t]);
        coboara(t);
    }
}


bool cmp(oaie a, oaie b)
{
	if(a.km==b.km)
		return a.kg>b.kg;
	return a.km>b.km;
}

int main()
{
	long long n,x,l,i;
	in>>n>>x>>l;
	for(long long i=1;i<=n;i++)
		in>>oi[i].km>>oi[i].kg;
	sort(oi+1,oi+n+1,cmp);
	long long miscari=0;
	for(i=1;i<=n;i++)
	{
		if(oi[i].km+miscari*l<=x)
		{
			h[++nh]=oi[i].kg;
			miscari++;
			urca(nh);
		}
		else
		{
			if(oi[i].kg>h[1])
			{
				h[++nh]=oi[i].kg;
				schimb(h[1],h[nh--]);
				coboara(1);
			}
		}
	}
	long long sum=0;
	for(i=1;i<=nh;i++)
		sum+=h[i];
	out<<sum;
	return 0;
}