Pagini recente » Cod sursa (job #1850583) | Cod sursa (job #239598) | Cod sursa (job #1011596) | Cod sursa (job #752191) | Cod sursa (job #2117383)
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 100000
using namespace std;
int heap[MAXN],poz[MAXN],d[MAXN],el[MAXN],gr[MAXN],dim;
inline bool cmp(int x,int y)
{
return gr[x]>gr[y];
}
inline void up(int p)
{
int x;
while((x=p>>1) && d[heap[p]]>d[heap[x]])
{
swap(poz[heap[p]],poz[heap[x]]);
swap(heap[p],heap[x]);
p=x;
}
}
inline void down(int p)
{
int x,maxim;
bool ok=true;
while((x=p<<1)<=dim && ok)
{
ok=false;
if(x<dim && d[heap[x+1]]>d[heap[x]])
maxim=x+1;
else
maxim=x;
if(d[heap[maxim]]>d[heap[p]])
{
swap(poz[heap[maxim]],poz[heap[p]]);
swap(heap[maxim],heap[p]);
p=maxim;ok=true;
}
}
}
int main()
{
FILE *fin,*fout;
fin=fopen("lupu.in","r");
fout=fopen("lupu.out","w");
int n,x,l,dist,grupa=0,i;
long long s=0;
fscanf(fin,"%d%d%d",&n,&x,&l);
for(i=0;i<n;i++)
{
fscanf(fin,"%d%d",&dist,&d[i]);
el[i]=i;
if(x-dist>=0)
gr[i]=(x-dist)/l+1;
else
gr[i]=0;
grupa=max(grupa,gr[i]);
}
sort(el,el+n,cmp);
i=0;
for(;grupa;grupa--)
{
while(i<n && gr[el[i]]==grupa)
{
poz[el[i]]=++dim;heap[dim]=el[i];
up(dim);i++;
}
if(dim)
{
s+=d[heap[1]];
swap(poz[heap[1]],poz[heap[dim]]);
swap(heap[1],heap[dim]);
dim--;down(1);
}
}
fprintf(fout,"%lld",s);
fclose(fin);
fclose(fout);
return 0;
}