Pagini recente » Cod sursa (job #2157575) | Cod sursa (job #2419142) | Cod sursa (job #1275775) | Cod sursa (job #11006) | Cod sursa (job #1257506)
#include<fstream>
#include<algorithm>
using namespace std;
const int NM = 100005;
int ln[NM],t[NM],I[NM];
int h[NM],hp;
inline void swap(int &a,int &b){ int k=a; a=b; b=k; }
struct cmp{
bool operator()(const int &i,const int &j){
return t[i] > t[j];
}
};
void upheap(int k){
while(k > 1 && h[k] > h[k/2])
{
swap(h[k], h[k/2]);
k /= 2;
}
}
void downheap(int k){
int nod=1;
while(nod)
{
nod=0;
if(2*k <= hp)
{
nod=2*k;
if(2*k+1 <= hp && h[nod] < h[nod+1]) ++nod;
if(h[nod] <= h[k]) nod=0;
}
if(nod)
{
swap(h[nod],h[k]);
k=nod;
}
}
}
int main(void){
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int N,L,X,i,j,tmax=0,x;
long long cost=0;
fin >> N >> X >> L;
for(i=1;i<=N;++i)
{
fin >> x >> ln[i];
t[i] = (X-x) / L;
if(t[i] > tmax) tmax=t[i];
I[i] = i;
}
sort(I+1,I+N+1,cmp());
for(j=tmax,i=1;j>=0;--j)
{
while(t[I[i]] == j && i <= N)
{
h[++hp]=ln[I[i]];
upheap(hp);
++i;
}
if(hp)
{
cost += h[1];
h[1] = h[hp--];
downheap(1);
}
}
fout << cost << '\n';
return 0;
}