Pagini recente » Cod sursa (job #709831) | Cod sursa (job #2261332) | Cod sursa (job #2028759) | Cod sursa (job #1384842) | Cod sursa (job #1435483)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("lupu.in");
ofstream out("lupu.out");
int n,x,d,l,h[200010];
int fs,p,nh=0,bun,scor;
struct oaie{
int dist;
int lana;};
oaie v[200010];
int cmp(oaie a,oaie b)
{
return (a.dist>b.dist);
}
void schimb(int p, int q)
{
int aux=h[p];
h[p]=h[q];
h[q]=aux;
}
void urca(int p)
{
while(p>1 && h[p]<h[p/2])
{
schimb(p,p/2);
p/=2;
}
}
void coboara(int p)
{
int fs=2*p,fd=2*p+1,bun=p;
if(fs<=nh && h[fs]<h[bun])
bun=fs;
if(fd<=nh && h[fd]<h[bun])
bun=fd;
if(bun!=p)
{
schimb(p,bun);
coboara(bun);
}
}
void citire()
{
in>>n>>x>>l;
for(int i=1;i<=n;i++)
{
in>>v[i].dist>>v[i].lana;
}
}
int main()
{
citire();
int i,j,t;
sort(v+1,v+n+1,cmp);
t=0;
scor=0;
for(i=1;i<=n;i++)
{
if(v[i].dist+t*l<=x)
{
h[++nh]=v[i].lana;
urca(nh);
t++;
scor+=v[i].lana;
}
else
if(v[i].lana>h[i])
{
scor+=v[i].lana-h[1];
h[1]=v[i].lana;
coboara(1);
}
}
out<<scor;
return 0;
}