Cod sursa(job #2839810)

Utilizator seburebu111Mustata Dumtru Sebastian seburebu111 Data 26 ianuarie 2022 16:51:56
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

const int N=1e5+2;

struct oaie{
    int d, l;
}oi[N];

priority_queue <int, vector<int>, greater<int>> h;

bool comp(oaie x, oaie y)
{
    return x.d>y.d;
}

int main()
{
    int n, dmax, dc;
    in>>n>>dmax>>dc;
    for(int i=1; i<=n; i++)
    {
        in>>oi[i].d>>oi[i].l;
    }

    sort(oi+1, oi+n+1, comp);
    int timp_c=0;
    long long lana = 0;
    for(int i=1; i<=n; i++)
    {
        long long distanta = oi[i].d + (long long)timp_c*dc;
        if(distanta<=dmax)
        {
            lana+=oi[i].l;
            h.push(oi[i].l);
            timp_c++;
        }
        else
        {
            if(!h.empty() && oi[i].l > h.top())
            {
                lana += oi[i].l - h.top();
                h.pop();
                h.push(oi[i].l);
            }
        }
    }
    out<<lana;
    return 0;
}