Pagini recente » Cod sursa (job #549102) | Cod sursa (job #1375720) | Cod sursa (job #2692480) | Cod sursa (job #3228680) | Cod sursa (job #1227701)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("lupu.in","r");
FILE *g=fopen("lupu.out","w");
int n,x,l,nr,tot,minim;
int heap[266001];
struct oaie {int dist;
int lana;};
oaie v[100001];
inline void coboara(int nod)
{int lt=v[heap[nod]].lana;
int lf1=v[heap[nod*2]].lana,lf2=v[heap[nod*2+1]].lana;
if (lt<max(lf1,lf2)) {if (lf1>lf2) {swap(heap[nod],heap[nod*2]);
coboara(nod*2);}
else {swap(heap[nod],heap[nod*2+1]);
coboara(nod*2+1);}
}
}
inline void urca(int nod)
{if (nod==1) return;
if (v[heap[nod]].lana>v[heap[nod/2]].lana) {swap(heap[nod],heap[nod/2]);
urca(nod/2);}
}
inline bool comp(const oaie &a,const oaie &b)
{if (a.dist>b.dist) return true;
return false;
}
int main()
{int i,j;
fscanf(f,"%d %d %d",&n,&x,&l);
for (i=1;i<=n;i++) fscanf(f,"%d %d",&v[i].dist,&v[i].lana);
sort(v+1,v+n+1,comp);
i=1;
minim=l;
while (i<=n)
{
while (i<=n&&v[i].dist+nr*l<=x&&x-v[i].dist<minim) {heap[i]=i;
urca(i);
i++;
}
minim+=l;
if (heap[1]!=0) {tot+=v[heap[1]].lana;
heap[1]=0;
coboara(1);
nr++;
}
while (heap[1]!=0&&v[heap[1]].dist+nr*l>x) {heap[1]=0;
coboara(1);}
}
while (heap[1]!=0)
{nr++;
tot+=v[heap[1]].lana;
heap[1]=0;
coboara(1);
while (heap[1]!=0&&v[heap[1]].dist+nr*l>x) {heap[1]=0;
coboara(1);}
}
fprintf(g,"%d\n",tot);
return 0;}