Cod sursa(job #2847976)

Utilizator CelestinNegraru Celestin Celestin Data 11 februarie 2022 21:45:02
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#define maxi 100005
using namespace std;
long long
ifstream f;
ofstream g;
struct oitza{
     long long distanta;
     long long cantitate;
};
oitza v[maxi];
priority_queue<pair<long long,long long>> maxheap;
ll n,range,l;
bool cmp(oitza A,oitza B)
{
    return(A.distanta<B.distanta);
}
void read()
{
    f.open("lupu.in",ios::in);
    f>>n>>range>>l;
    for(int i=1;i<=n;i++)
    {
        f>>v[i].distanta>>v[i].cantitate;
    }
    f.close();
    return;
}
long long greedy()
{
    long long ans=0;
    read();
    sort(v+1,v+n+1,cmp);
    int cnt=1;
    while(v[cnt].distanta<=range&&cnt<=n)
    {
        maxheap.push(make_pair(v[cnt].cantitate,v[cnt].distanta));
        cnt++;
    }
    long long bonus=0;
    while(!maxheap.empty())
    {
        while(maxheap.top().second+bonus>range&&maxheap.size())
        {
            maxheap.pop();
        }
        if(maxheap.size())
        {
            if(maxheap.top().second+bonus<=range)
               {
            ans+=maxheap.top().first;
            maxheap.pop();
            bonus+=l;
               }
        }
    }
    return ans;
}
int main()
{
    g.open("lupu.out",ios::out);
    g<<greedy();
    g.close();
    return 0;
}