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