Cod sursa(job #3300856)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 19 iunie 2025 15:07:50
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#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;
}