Pagini recente » Cod sursa (job #3291753) | ONIS 2014, Runda 2 | Cod sursa (job #1279489) | Rezultatele filtrării | Cod sursa (job #3300856)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 500001;
vector<pair<int, int>> tmax;
int heap[NMAX], heap_size;
void check_up(int node_position)
{
int dad_position = node_position / 2;
if (dad_position == 0)
return;
if (heap[dad_position] < heap[node_position])
{
swap(heap[dad_position], heap[node_position]);
check_up(dad_position);
}
}
void check_down(int node_position)
{
int left_son = node_position * 2;
int right_son = left_son + 1;
int current_max = heap[node_position], min_case = 0;
if (left_son <= heap_size && current_max < heap[left_son])
{
current_max = heap[left_son];
min_case = 1;
}
if (right_son <= heap_size && current_max < heap[right_son])
{
current_max = heap[right_son];
min_case = 2;
}
if (min_case == 1)
{
swap(heap[node_position], heap[left_son]);
check_down(left_son);
}
else if (min_case == 2)
{
swap(heap[node_position], heap[right_son]);
check_down(right_son);
}
}
void insert(int value)
{
heap[++heap_size] = value;
check_up(heap_size);
}
int pop()
{
int root_value = heap[1];
heap[1] = heap[heap_size];
heap_size--;
check_down(1);
return root_value;
}
bool comp(pair<int, int> a, pair<int, int> b)
{
return (a.first > b.first);
}
int main()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
int i, n, x, l;
scanf("%d %d %d", &n, &x, &l);
for (i = 0; i < n; i++)
{
int d, a;
scanf("%d %d", &d, &a);
if (d <= x)
{
tmax.push_back({(x - d) / l + 1, a});
}
}
sort(tmax.begin(), tmax.end(), comp);
unsigned long long int suma = 0;
i = 0;
for (int current_time = tmax[0].first; current_time > 0; --current_time)
{
while (i < n && tmax[i].first == current_time)
{
insert(tmax[i].second);
i++;
}
if (heap_size > 0)
{
suma += pop();
}
}
printf("%lld\n", suma);
return 0;
}