Pagini recente » Cod sursa (job #1747172) | Cod sursa (job #418350) | Cod sursa (job #710023) | Cod sursa (job #11369) | Cod sursa (job #333252)
Cod sursa(job #333252)
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
#define mp make_pair
#define nx 100005
#define inf
using namespace std;
vector <pair <int,int> > a;
int n,x,l,heap[nx],L;
long long sol;
struct asd
{
int tim,poz;
};
asd t[nx];
bool cmp (const asd &a,const asd &b)
{
return a.tim>b.tim;
}
void upheap (int x)
{
int aux;
while (x/2 && a[heap[x]].second>a[heap[x/2]].second)
{
aux=heap[x];
heap[x]=heap[x/2];
heap[x/2]=aux;
}
}
void downheap(int x)
{
int y=0,aux;
while (y!=x)
{
y=x;
if (y*2<=L && a[heap[y*2]].second>a[heap[x]].second)
x=y*2;
if (y*2+1<=L && a[heap[y*2+1]].second>a[heap[x]].second)
x=y*2+1;
aux=heap[x];
heap[x]=heap[y];
heap[y]=aux;
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
int i,p,q,j;a.pb(mp(0,0));
for (i=1;i<=n;++i)
{
scanf("%d%d",&p,&q);
a.pb(mp(p,q));
if (p>x) t[i].tim=-1;
else t[i].tim=(x-p)/l;
t[i].poz=i;
}
sort(t+1,t+n+1,cmp);
for (i=1;t[1].tim>=0;t[1].tim--)
{
if (t[i].tim>-1) {
heap[++L]=t[i].poz;
upheap(L);
for (j=i+1;j<=n && t[j].tim==t[i].tim;++j)
{
heap[++L]=t[j].poz;
upheap(L);
} i=j-1; i++;}
if (L>0)
{
sol+=a[heap[1]].second;
heap[1]=heap[L--];
downheap(1);
}
}
printf("%lld\n",sol);
return 0;
}