Pagini recente » Cod sursa (job #1844204) | Cod sursa (job #1243020) | Cod sursa (job #1806052) | Cod sursa (job #2192747) | Cod sursa (job #1515530)
#include <cstdio>
#include <algorithm>
#define LIM 100023
using namespace std;
long long t[LIM],heap[LIM];
long long a[LIM];
struct str
{
long long val;
long long pos;
}srt[LIM];
long long n,x,l,temp,m,lmt;
long long tata(long long a)
{
return a/2;
}
void checkup(long long pos)
{
while(tata(pos)!=0&&a[heap[pos]]>a[heap[tata(pos)]])
{
swap(heap[pos],heap[tata(pos)]);
pos=tata(pos);
if(pos==0) return;
}
}
void add(long long pos)
{
heap[++m]=pos;
checkup(m);
}
void checkdown()
{
long long nod=1;
while(nod<=m)
{
long long best=0;
long long st=nod*2,dr=nod*2+1;
if(st<=m&&a[heap[nod]]<a[heap[st]]) best=1;
if(best==0&&dr<=m&&a[heap[nod]]<a[heap[dr]]) best=2;
if(best==1&&dr<=m&&a[heap[st]]<a[heap[dr]]) best=2;
if(best==0) return;
if(best==1)
{
swap(heap[nod],heap[st]);
nod=st;
}
else if(best==2)
{
swap(heap[nod],heap[dr]);
nod=dr;
}
}
}
void rem()
{
swap(heap[1],heap[m]);
m--;
if(m==0) return;
checkdown();
}
long long comp(str a,str b)
{
return a.val>b.val;
}
int main()
{
freopen ("lupu.in","r",stdin);
freopen ("lupu.out","w",stdout);
scanf("%lld%lld%lld",&n,&x,&l);
lmt=x/l+2;
for(long long i=1;i<=n;i++)
{
++temp;
scanf("%lld%lld",&t[temp],&a[temp]);
while(t[temp]>x)
{
scanf("%lld%lld",&t[temp],&a[temp]);
}
t[i]=(x-t[i])/l+1;
}
for(long long i=1;i<=temp;i++)
{
srt[i].val=t[i];
srt[i].pos=i;
}
n=temp;
sort(srt+1,srt+temp+1,comp);
// for(long long i=1;i<=temp;i++)
// {
// printf("%d %d %d\n",srt[i].pos,srt[i].val,a[srt[i].pos]);
// }
long long pst=1;
long long sum=0;
// printf("%d\n",lmt);
for(long long i=lmt;i>=1;i--)
{
/// printf("%d %d\n",srt[pst].pos,i);
if(srt[pst].val==i&&pst<=n)
{
while(srt[pst].val==i)
{
add(srt[pst].pos);
pst++;
if(pst>n) break;
}
}
if(m>=1)
{
// printf("%d\n",a[heap[1]]);
sum+=a[heap[1]];
rem();
}
}
printf("%lld\n",sum);
}