Cod sursa(job #3300777)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 18 iunie 2025 22:46:37
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#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 (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);
    }

    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);
            // cout << heap[1] << ' ';
            i++;
        }
        // printf("%d -> %d\n", i, heap[1]);

        if (heap_size > 0)
            suma += pop();
    }
    printf("%d", suma);
    return 0;
}