Pagini recente » Cod sursa (job #1642480) | Cod sursa (job #2568967) | Cod sursa (job #3176415) | Cod sursa (job #415527) | Cod sursa (job #2031587)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct oaie{
int cant;
int strat;
};
int n,x,st,l,i,j,d,a,nrel,h[100005];
long long total;
oaie v[100005];
bool cmp(oaie a, oaie b)
{
if (a.strat<b.strat) return 1;
else return 0;
}
void urca()
{
int poz=nrel;
while (poz>1 && h[poz]>h[poz/2])
{
swap(h[poz],h[poz/2]);
poz=poz/2;
}
}
void coboara()
{
int poz=1;
while (h[2*poz]>h[poz] or h[2*poz+1]>h[poz] && poz<nrel)
{
if (h[2*poz]>h[poz])
{
swap(h[2*poz],h[poz]);
poz=2*poz;
}
else
{
swap(h[2*poz+1],h[poz]);
poz=2*poz+1;
}
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for (i=1; i<=n; i++)
{
scanf("%d%d",&d,&a);
v[i].cant=a;
v[i].strat=d+l-1/l;
}
sort(v+1,v+n+1,cmp);
j=1;
for (i=0; i<=x/l; i++)
{
//iau toate oile de pe stratul al i-lea si le bag in heap
st=v[j].strat;
while (j<=n && v[j].strat==st)
{
h[++nrel]=v[j++].cant;
urca();
}
if (nrel>0) {total=total+1ll*h[1];
h[1]=h[nrel--];}
coboara();
}
printf("%lld\n",total);
return 0;
}