Pagini recente » Cod sursa (job #1885693) | Cod sursa (job #1611949) | Cod sursa (job #1603546) | Cod sursa (job #1566971) | Cod sursa (job #1318664)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int i,n,m;
long long D,L,s,h[100001];
struct oaie
{
long long d,l;
}v[100002];
void interschimb(int i,int j)
{
int x=h[i];
h[i]=h[j];
h[j]=x;
}
void up (int i)
{
while(h[i]<h[i/2]&&i>=2)
interschimb(i,i/2),i/=2;
}
void down (int i)
{
int x=2*i+1,y=2*i;
int k=i;
if(h[x]<k&&x<=m)
k=x;
if(h[y]<k&&y<=m)
k=y;
if(k!=i)
interschimb(i,k),down(k);
}
bool compar(oaie a,oaie b)
{
return a.d<b.d;
}
int main()
{f>>n>>D>>L;
for(i=1;i<=n;i++)
f>>v[i].d>>v[i].l,v[i].d=(D-v[i].d)/L;
sort(v,v+n+1,compar);
m=1;
h[m]=v[1].l;
for(i=2;i<=n;i++)
{
if(m<=v[i].d)
m++,h[m]=v[i].l,up(m);
else
if(h[1]<v[i].l)
h[1]=v[i].l,down(1);
}
s=0;
for(i=1;i<=m;i++)
s+=h[i];
g<<s;
return 0;
}