Pagini recente » Cod sursa (job #715475) | Cod sursa (job #1424539) | Cod sursa (job #807658) | Cod sursa (job #131710) | Cod sursa (job #1303334)
#include <fstream>
#include <cstdio>
#include <algorithm>
#define nmax 150005
using namespace std;
ifstream f("lupu.in");
FILE *g=fopen("lupu.out","w");
int n,x,l;
long long sol;
struct oaie {int d;int p;};
oaie v[nmax];
int heap[nmax],k;
void urca(int C)
{int P=C/2;
while (P>0)
{if (heap[C]>heap[P]) {
swap(heap[C],heap[P]);
C=P;
P/=2;}
else break;
}
}
void coboara(int P)
{int C;
C=P*2;
while (C<=k) {
if (C+1<=k&&heap[C+1]>heap[C]) C=C+1;
if (heap[P]<heap[C])
{swap(heap[P],heap[C]);
P=C;
C=C*2;
}
else break;
}
}
bool cmp(const oaie &a,const oaie &b)
{return a.d>b.d;}
int main(){
int i,j;
f>>n>>x>>l;
for (i=1;i<=n;i++)
{v[i].d/=l;
if (v[i].d>x) {i--;n--;}
else {
f>>v[i].d>>v[i].p;
v[i].d=x-v[i].d;
v[i].d/=l;
v[i].d++;
}
}
sort(v+1,v+n+1,cmp);
j=v[1].d;
i=1;
while (j>=1)
{while (v[i].d>=j) {heap[++k]=v[i].p;
urca(k);
i++;}
sol+=1LL*heap[1];
heap[1]=heap[k];
heap[k]=0;
k--;
coboara(1);
j--;
}
fprintf(g,"%lld",sol);
return 0;
}