Cod sursa(job #3265728)

Utilizator tedicTheodor Ciobanu tedic Data 2 ianuarie 2025 18:48:28
Problema Lupul Urias si Rau Scor 72
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;
ifstream cin("lupu.in");
ofstream cout("lupu.out");
struct oaie
{
    long long int expirare,lana;
} v[100005];
priority_queue<int>oi;
bool cmp(oaie x, oaie y)
{
    if(x.expirare!=y.expirare)
        return x.expirare<y.expirare;
    return x.lana>y.lana;
}
int main()
{
    long long int n,x,l,dist;
    long long int sol=0;
    cin>>n>>x>>l;
    for(int i=1; i<=n; i++)
    {
        cin>>dist>>v[i].lana;
        if(dist<=x)
            v[i].expirare=(x-dist)/l;
        else
            v[i].expirare=-1;
    }
    sort(v+1,v+1+n,cmp);
    if(v[1].expirare==v[n].expirare)
    {
        for(int i=n; i>=1 && v[n].expirare>=0; i--)
            sol+=v[i].lana,v[n].expirare--;
    }

    //sol+=v[n].lana;
    else
    {
        int poz=0;
        oi.push(v[n].lana);
        for(int i=n; i>=1; i--)
        {
            if(i<n && v[i].expirare==v[i+1].expirare)
            {
                oi.push(v[i].lana);
                continue;
            }
            while(!oi.empty() && v[i+1].expirare>v[i].expirare)
            {
                //cout<<sol<<'\n';
                //  cout<<v[i].expirare<<" "<<v[i].lana<<'\n';
                v[i+1].expirare--;
                sol+=oi.top();
                oi.pop();
            }
            oi.push(v[i].lana);
        }
        while(!oi.empty() && v[1].expirare>=0)
        {
            //cout<<sol<<'\n';
            //  cout<<v[i].expirare<<" "<<v[i].lana<<'\n';
            v[1].expirare--;
            sol+=oi.top();
            oi.pop();
        }
    }
    cout<<sol;
    return 0;
}