Pagini recente » Cod sursa (job #623110) | Cod sursa (job #2581629) | Cod sursa (job #192762) | Cod sursa (job #2372130) | Cod sursa (job #769163)
Cod sursa(job #769163)
#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){
if(h[2*k]>h[k] && h[2*k]>h[2*k+1]){
swap(h[k],h[2*k]);
if(2*k<hp)downheap(2*k);
}
else if(h[2*k+1]>h[k] && h[2*k+1]>=h[2*k]){
swap(h[k],h[2*k+1]);
if(2*k+1<hp)downheap(2*k+1);
}
}
void insert(int k){
h[++hp]=k; upheap(hp);
}
void del(){
swap(h[1],h[hp]); h[hp]=-1; --hp; downheap(1);
}
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)/2;
if(t[i]>tmax)tmax=t[i];
I[i]=i;
}
sort(I+1,I+N+1,cmp()); h[0]=-1;
for(j=tmax,i=1;j>=0;--j)
{
while(t[I[i]]==j && i<=N){ insert(ln[I[i]]); ++i; }
if(hp>0)
{
cost+=h[1];
del();
}
}
fout<<cost;
return 0;
}