Pagini recente » Cod sursa (job #2331121) | Cod sursa (job #586631) | Cod sursa (job #2918151) | Cod sursa (job #375798) | Cod sursa (job #3300850)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100001;
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; /* <----------- ASTA LIPSEA
* radacina este la pozitia 1, dad_position poate fi 0 doar daca node_position este 1, dar radacina nu are tata
fara linia asta, in inserturi radacina era la pozitia 0 si in pop radacina era considerata la pozitia 1, motiv pentru care iti dadea niste numere random
*/
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)
{
if (a.first > b.first)
{
return true;
}
return false;
}
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);
tmax.push_back({(x - d) / l + 1, a});
}
sort(tmax.begin(), tmax.end(), comp);
/*for (auto i : tmax)
{
printf("%d %d\n", i.first, i.second);
}*/
long long int suma = 0;
i = 0;
while (i < n)
{
int current_time = tmax[i].first;
while (i < n && tmax[i].first == current_time)
{
insert(tmax[i].second);
i++;
}
// printf("%d -> %d\n", i, heap[1]);
if (heap_size > 0)
suma += (long long int)pop();
}
printf("%lld", suma);
return 0;
}