Cod sursa(job #2032816)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 5 octombrie 2017 18:42:40
Problema Lupul Urias si Rau Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define DIM 100002

using namespace std;

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

int n;

long long s, x, l, val, maxim;

struct oaie
{
    long long d, lana;
}oi[DIM];

vector <int> v[DIM];

bool cmp(int a, int b)
{
    return oi[a].lana > oi[b].lana;
}

priority_queue <long long> h;

int main()
{
    f>>n>>x>>l;

    for(int i = 1; i <= n; ++ i)
    {
        f>>oi[i].d>>oi[i].lana;
        val = (x - oi[i].d) / l;
        if(maxim < val)
            maxim = val;
        if(val > 0)
        {
            v[val].push_back(i);
        }
    }

    for(int i = 1; i <= n; ++ i)
        sort(v[i].begin(), v[i].end(), cmp);

    for(int i = 0; i <= maxim; ++ i)
    {
        for(int j = 0; j < v[i].size() && j <= i; ++ j)
        {
            h.push(oi[v[i][j]].lana);
        }
    }

    for(int i = 0; i <= maxim && !h.empty(); ++i)
    {
        s += h.top();
        h.pop();
    }

    g<<s;

    return 0;
}