Pagini recente » Cod sursa (job #1983176) | Cod sursa (job #838794) | Cod sursa (job #2317861) | Cod sursa (job #367586) | Cod sursa (job #837683)
Cod sursa(job #837683)
#include <fstream>
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 100001
#define left_son i << 1
#define right_son (i << 1) + 1
using namespace std;
typedef struct
{
int t;
int l;
}oaie;
bool cmp(oaie a ,oaie b)
{
return a.t < b.t;
}
oaie vect[MAX_SIZE];
int heap[MAX_SIZE];
int nh;
int N, X , L;
long long answer = 0;
void up_heap(int i)
{
if ( i <= 1 ) return;
if ( heap[i] > heap[ i >> 1] )
{
swap( heap[i] , heap[i >> 1]);
up_heap(i >> 1);
}
}
void down_heap(int i)
{
int m = i;
if ( left_son <= nh && heap[left_son] > heap[m]) m = left_son;
if ( right_son <= nh && heap[right_son] > heap[m]) m = right_son;
if (m != i)
{
swap( heap[i] , heap[m]);
down_heap(m);
}
}
int main()
{
ifstream input("lupu.in");
ofstream output("lupu.out");
input >> N >> X >> L;
for (int i =1;i<=N;i++)
{
int d , a;
input >> d >> a;
vect[i].t = (X- d) / L + 1;
vect[i].l = a;
}
sort(vect+1 ,vect+N+1, cmp);
int tmax = vect[N].t;
int last = N;
nh = 0;
for (int i = tmax;i>0;i--)
{
while ( last > 0 && vect[last].t == i)
{
nh ++;
heap[nh] = vect[last].l;
up_heap(nh);
last --;
}
if (nh != 0)
{
answer += heap[1];
swap(heap[1],heap[nh--]);
down_heap(1);
}
}
output << answer;
return 0;
}