Cod sursa(job #2472738)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 12 octombrie 2019 19:36:35
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

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

struct pr
{
    int val, timp;
};

pr v[100001];
int n,x,k;
long long sol;

bool b(pr a, pr b)
{
    return a.val < b.val;
}

bool descr(pr const& a, pr const& b)
{
    if(a.timp != b.timp)
        return a.timp > b.timp;
    return a.val > b.val;
}

void citire()
{
    cin >> n >> x >> k;
    for(int i = 0 ; i < n ; i++)
        cin >> v[i].timp >> v[i].val;
    sort(v, v + n, descr);
}

void rez()
{
    priority_queue<pr, vector<pr>, bool(*)(pr, pr)> q(b);

    int nr = 0, i = 0;

    for(int i = 0 ; i < n ; i++)
        q.push(v[i]);

    while(!q.empty() && nr <= x)
    {
        while(!q.empty() && q.top().timp + nr > x)
            q.pop();

        if(!q.empty())
            sol += q.top().val, q.pop();

        nr += k;
    }

    cout << sol;
}

int main()
{
   citire();
   rez();
   return 0;
}