Cod sursa(job #2566200)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 2 martie 2020 19:28:04
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream in ("lupu.in");
ofstream out ("lupu.out");

const int N=100001;
struct oaie
{
    int d,c;
}oi[N];
priority_queue <int> q;

bool comp (oaie a, oaie b)
{
    if (a.d<b.d) return true;
    if (a.d==b.d)
        if (a.c>b.c) return true;
    return false;
}
int main()
{
    int n,x,l,k=0,a,b;
    int T=0;
    in>>n>>x>>l;
    for (int i=1;i<=n;i++)
    {
        in>>a>>b;
        if (a<=x)
        {
            oi[k].d=(x-a)/l+1;
            T=max(T,oi[k].d);
            oi[k++].c=b;
        }
    }
    sort (oi,oi+k,comp);
    long long cant=0;
    int i=k-1;
    for (int t=T;t>0 && i>=0;t--)
    {
        while (i>=0 && oi[i].d==t)
        {
            q.push(oi[i].c);
            i--;
        }
        if (!q.empty())
        {
            cant+=q.top();
            q.pop();
        }
    }
    out<<cant;
    return 0;
}