Cod sursa(job #2925911)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 16 octombrie 2022 13:18:24
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;

using namespace std;

/*******************************/
// INPUT / OUTPUT

ifstream f("lupu.in");
ofstream g("lupu.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N, X, L;
ll ans;
struct Oaie
{
    int zi, lana, idx;

    bool operator < (const Oaie &other) const {
        if (lana == other.lana)
        {
            return idx < other.idx;
        }
        return lana < other.lana;
    }
};

vector <Oaie> oi;
priority_queue <Oaie> pq;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N >> X >> L;

    int zi, dist, lana;
    for (int i = 0 ; i < N ; ++ i)
    {
        f >> dist >> lana;
        if (dist > X) continue;
        zi = (X - dist) / L;
        oi.push_back({zi, lana, i});
    }

    N = oi.size();
}
///-------------------------------------
bool cmp(const Oaie &a, const Oaie &b)
{
    if (a.zi == b.zi)
    {
        return a.idx < b.idx;
    }
    return a.zi > b.zi;
}
///-------------------------------------
inline void Solution()
{
    sort(oi.begin(), oi.end(), cmp);

    int i = 0;
    int lana_top;
    for (int zi = X / L ; zi >= 0 ; -- zi)
    {
        while (i < N && oi[i].zi == zi)
        {
            pq.push(oi[i]);
            i ++;
        }

        if (!pq.empty())
        {
            lana_top = pq.top().lana;
            pq.pop();

            ans += 1LL * lana_top;
        }
    }
}   
///-------------------------------------
inline void Output()
{
    g << ans;
}
///-------------------------------------
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ReadInput();
    Solution();
    Output();
    return 0;
}