Cod sursa(job #2861417)

Utilizator CelestinNegraru Celestin Celestin Data 3 martie 2022 22:21:33
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define maxi 100005
using namespace std;
fstream f,g;
struct oaie{
    int distanta;
    int cantitate;
};
oaie v[maxi];
bool cmp(oaie A,oaie B)
{
    return(A.distanta>B.distanta);
}
priority_queue<int,vector<int>,greater<int>> minheap;
int n,x,l;
long long ans,ratie;
void read()
{
    f.open("lupu.in",ios::in);
    f>>n>>x>>l;
    for(int i=1;i<=n;i++)
    {
        f>>v[i].distanta>>v[i].cantitate;
    }
    f.close();
    return;
}
long long greedy()
{
    g.open("lupu.out",ios::out);
    read();
    sort(v+1,v+n+1,cmp);
    int i=1;
    for(;i<=n;i++)
        {
            while(v[i].distanta+ratie<=x&&i<=n)
            {
                minheap.push(v[i].cantitate);
                ans+=v[i].cantitate;
                ratie+=l;
                i++;
            }
            if(minheap.size())
            {
                if(v[i].distanta+ratie-l<=x&&v[i].cantitate>minheap.top())
                {
                   ans-=minheap.top();
                   minheap.pop();
                   ans+=v[i].cantitate;
                   minheap.push(v[i].cantitate);
                }
            }
        }
    g<<ans;
    g.close();
    return;
}
int main()
{
    greedy();
    return 0;
}