Cod sursa(job #2401322)

Utilizator DorianPopDorian Pop DorianPop Data 9 aprilie 2019 16:49:07
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

struct oaie
{
    long long dist, lana, timp;
    bool operator<(oaie rhs) const
    {
        return lana<rhs.lana;
    }
} p[100002];

bool comp_t(oaie s, oaie dr)
{
    return s.timp>dr.timp;
}

priority_queue<oaie> q;
long long N, X, L, ans, tmax;
int main()
{
    fin>>N>>X>>L;
    for (int i=1; i<=N; i++)
    {
        fin>>p[i].dist;
        fin>>p[i].lana;
        p[i].timp = (X-p[i].dist)/L;
        if (p[i].timp>tmax)
            tmax = p[i].timp;
    }

    sort(p+1,p+N+1, comp_t);

    long long pos = 1;
    for (long long d=tmax; d>=0; d--)
    {
        while (pos<=N && p[pos].timp==d)
        {
            q.push(p[pos]);
            pos++;
        }
        if (!q.empty())
        {
            ans+=q.top().lana;
            q.pop();
        }
    }
    fout<<ans;
}