Pagini recente » Cod sursa (job #479870) | Cod sursa (job #2016026) | Cod sursa (job #488546) | Cod sursa (job #1381878) | Cod sursa (job #1425064)
#include <fstream>
#include <algorithm>
#define dim 100001
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
long long sum;
int lana[dim],i,j,dist,n,x1,l,Max1,val,heap[dim],Max,poz,t,k;
struct cub
{
int x;
int y;
}timp[dim];
int cmp(cub o, cub p)
{
return o.x>p.x;
}
void upDate(int poz)
{
while(poz/2>0)
{
if(heap[poz]>heap[poz/2])
{
swap(heap[poz],heap[poz/2]);
poz/=2;
}
else
break;
}
}
void downDate(int poz)
{
int po;
while(poz*2<=k)
{
po=poz*2;
if(po+1<=k&&heap[po]<heap[po+1])
po++;
if(heap[poz]<heap[po])
{
swap(heap[po],heap[poz]);
poz=po;
}
else
break;
}
}
int main()
{
fin>>n>>x1>>l;
for(i=1;i<=n;i++)
{
fin>>dist>>lana[i];
if(dist<=x1)
{
if(dist==x1)
timp[i].x=1;
else
timp[i].x=(x1-dist)/l+1;
}
else
timp[i].x=0;
if(timp[i].x>Max)
Max=timp[i].x;
timp[i].y=i;
}
sort(timp+1,timp+n+1,cmp);
poz=1;
for(j=Max;j>=1;j--)
{
for(t=poz;timp[t].x==j&&t<=n;t++)
{
heap[++k]=lana[timp[t].y];
upDate(k);
}
if(k>0)
{
sum+=heap[1];
swap(heap[1],heap[k]);
k--;
downDate(1);
}
poz=t;
}
fout<<sum;
return 0;
}