Cod sursa(job #3194625)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 18 ianuarie 2024 19:28:06
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin ("timbre.in");
ofstream fout("timbre.out");
long long n,m,k,i,x,j,y,c,sol;
priority_queue <int> Q;
struct elem
{
    int dr,cost;
}V[100003];
int main()
{
    fin>>n>>m>>k;
    for(i=1;i<=n;i++)
    {
        fin>>x>>V[i].cost;
        V[i].dr=(m-x)/k;
    }
    sort(V+1,V+n+1,[](elem a,elem b){
         if(a.dr==b.dr)
            return a.cost<b.cost;
         return a.dr<b.dr;
         });
    j=n;
    sol=0;
    for(i=V[n].dr;i>=0;i--)
    {
        while(j&&V[j].dr>=i)
        {
            Q.push(V[j].cost);
            j--;
        }
        if(!Q.empty())
        {
            sol+=Q.top();
            Q.pop();
        }
    }
    fout<<sol;
    return 0;
}