Pagini recente » Cod sursa (job #1423237) | Cod sursa (job #2894380) | Cod sursa (job #195526) | Cod sursa (job #2150032) | Cod sursa (job #474617)
Cod sursa(job #474617)
#include <fstream>
using namespace std;
struct oaie{int lana,dist;} v[1<<17],a[1<<17];
int m;
ifstream in("lupu.in");
ofstream out("lupu.out");
inline bool cmp(oaie a,oaie b)
{
return a.lana>b.lana || a.lana==b.lana && a.dist<b.dist;
}
inline void down(int x)
{
int q=x;
oaie aux;
if ((x<<1)<=m && cmp(v[x<<1],v[q]))
q=x<<1;
if ((x<<1)<m && cmp(v[(x<<1)+1],v[q]))
q=(x<<1)+1;
if (x!=q)
{
aux=v[x];
v[x]=v[q];
v[q]=aux;
down(q);
}
}
inline void up(int x)
{
if (x>1 && cmp(v[x],v[x>>1]))
{
oaie aux=v[x];
v[x]=v[x>>1];
v[x>>1]=aux;
up(x>>1);
}
}
bool comp(oaie a,oaie b)
{
return a.dist>b.dist;
}
int main()
{
int n,X,L,x,y,i,j,q=0,T=-1;
long long s=0;
in>>n>>X>>L;
while (n--)
{
in>>x>>y;
if (x<=X)
{
a[++q].dist=(X-x)/L+1;
a[q].lana=y;
T=max(T,a[q].dist);
}
}
sort(a+1,a+q+1,comp);
for (i=T,j=1;i;i--)
{
for (;j<=q && a[j].dist==i;j++)
{
v[++m]=a[j];
up(m);
}
while (m && v[1].dist<i)
{
v[1]=v[m--];
down(1);
}
if (m)
{
s+=v[1].lana;
v[1]=v[m--];
down(1);
}
}
out<<s<<"\n";
return 0;
}