Cod sursa(job #3265725)

Utilizator tedicTheodor Ciobanu tedic Data 2 ianuarie 2025 18:43:07
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 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;
    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[0].expirare>=0)
    {
        //cout<<sol<<'\n';
        //  cout<<v[i].expirare<<" "<<v[i].lana<<'\n';
        v[0].expirare--;
        sol+=oi.top();
        oi.pop();
    }
    }
    cout<<sol;
    return 0;
}