Pagini recente » Cod sursa (job #1074794) | Cod sursa (job #778405) | Cod sursa (job #685851) | Cod sursa (job #581301) | Cod sursa (job #769135)
Cod sursa(job #769135)
#include<fstream>
#include<algorithm>
using namespace std;
const int NM = 100005;
int d[NM],ln[NM],t[NM],I[NM];
int h[NM],poz[NM],v[NM],hp,n;
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 && v[h[k]]>v[h[k/2]])
{
swap(poz[h[k]],poz[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 && v[h[nod]]<v[h[nod+1]])++nod;
if(v[h[nod]]<=v[h[k]])nod=0;
}
if(nod)
{
swap(poz[h[nod]],poz[h[k]]);
swap(h[nod],h[k]);
k=nod;
}
}
}
void insert(int k){
v[++n]=k; h[++hp]=n; poz[n]=hp;
upheap(hp);
}
void del(int k){
poz[h[hp]]=k; swap(h[k],h[hp]); --hp;
if(k>1 && v[h[k]]>v[h[k/2]])upheap(k);
else downheap(k);
}
int main(void){
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int N,L,X,i,j,tmax=0; long long cost=0;
fin>>N>>X>>L;
for(i=1;i<=N;++i)
{
fin>>d[i]>>ln[i];
t[i]=(X-d[i])/2+1;
if(t[i]>tmax)tmax=t[i];
I[i]=i;
}
sort(I+1,I+N+1,cmp());
j=tmax; i=1;
while(j>0)
{
while(t[I[i]]==j && i<=N){ insert(ln[I[i]]); ++i; }
if(hp)
{
cost+=(long long)(v[h[1]]);
del(poz[v[h[1]]]);
}
--j;
}
fout<<cost<<'\n';
return 0;
}