Pagini recente » Cod sursa (job #1964936) | Cod sursa (job #2877252) | Simulare 39 | Cod sursa (job #1284092) | Cod sursa (job #2099820)
#include <iostream>
#include <algorithm>
#include <fstream>
#define x first
#define y second
#define MAX 100001
#define VMAX 10000000000
using namespace std;
typedef long long ll;
ll n,X,l,heap[MAX],sz,ans,nrp,ds,na;
pair<ll,ll> a[MAX];
void adauga(ll ind){
sz++;
heap[sz]=a[ind].y;
ll ii=sz;
while(sz/2>0&&heap[sz/2]<heap[sz])swap(heap[sz],heap[sz/2]),sz/=2;
}
void elimina(){
ans+=heap[1];
heap[1]=heap[sz];sz--;
ll ii=1;
while(ii*2<=sz){
ds=0;
if(heap[ii]<heap[ii*2])ds=ii*2;
if(ii*2+1<=sz&&heap[ii]<heap[ii*2+1]&&heap[ii*2+1]>heap[ii*2])ds=ii*2+1;
if(ds==0)break;
swap(heap[ii],heap[ds]);
ii=ds;
}
}
void afiseaza(int st,int dr){
if(st>sz)return;
for(int ii=st;ii<=dr&&ii<=sz;ii++)cout<<heap[ii]<<" ";
cout<<'\n';
afiseaza(st*2,dr*2+1);
}
int main()
{
ifstream f ("lupu.in");
ofstream g ("lupu.out");
f>>n>>X>>l;
for(int i=1;i<=n;i++){
f>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1);na=1;nrp=VMAX;
for(int i=1;nrp>=0&&i<=n;i++){
nrp=min(nrp,(X-a[i].x)/l);
for(;na<=n&&a[na].x+nrp*l<=X;na++)adauga(na);
//afiseaza(1,1);cout<<"--------\n";
if(sz>=0){
elimina();
nrp--;
//i=na;
}
}
g<<ans;
f.close ();
g.close ();
return 0;
}