Pagini recente » Cod sursa (job #291936) | Cod sursa (job #1326949) | Cod sursa (job #1082053) | Cod sursa (job #1584847) | Cod sursa (job #848709)
Cod sursa(job #848709)
#include <cstdio>
#include <cstdlib>
#define maxn 100001
#include <iostream>
using namespace std;
FILE*f=fopen("lupu.in","r");
FILE*g=fopen("lupu.out","w");
int n,x,l,d,heap[maxn],Tmax,indheap;
long long s;
typedef struct
{int t;
int l;}oaie;
oaie A[maxn];
bool comp(oaie a ,oaie b)
{
return a.t < b.t;
}
int max(int a,int b)
{
if (a>b)
return a;
return b;
}
void swap(int &a,int &b)
{
int aux;
aux=a;
a=b;
b=aux;
}
void up_heap(int x)
{
if (x==1)
return;
if (heap[x/2]<heap[x])
{
swap(heap[x/2],heap[x]);
up_heap(x/2);
}
}
void down_heap(int x)
{
int m=x;
if ((2*x<=indheap) && (heap[2*x]>heap[x]))
m=2*x;
if ((2*x+1<=indheap) && (heap[2*x+1]>heap[x]))
m=2*x+1;
if (m!=x)
{
swap(heap[m],heap[x]);
down_heap(m);
}
}
int main()
{
int k,x,l,i,j;
fscanf(f,"%d%d%d",&n,&x,&l);
s=0;
for (i=1;i<=n;i++)
{
fscanf(f,"%d%d",&d,&A[i].l);
A[i].t=(x-d)/l+1;
}
sort(A+1,A+n+1,comp);
Tmax=A[n].t;
indheap=0;j=n;
for (i=Tmax;i>0;i--)
{
while ((j>0) && (A[j].t==i))
{
indheap++;
heap[indheap]=A[j].l;
up_heap(indheap);
j--;
}
if (indheap!=0)
{
s+=heap[1];
swap(heap[1],heap[indheap]);
indheap--;
down_heap(1);
}
}
fprintf(g,"%lld",s);
return 0;
}