Cod sursa(job #2031105)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 2 octombrie 2017 19:00:44
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 100002

using namespace std;

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

long long n, x, lana, l;

long long s, dist, h[DIM], nn;

vector <long long> graf[DIM];

bool cmp(long long a, long long b)
{
    return a > b;
}

void percolate(long long val)
{
    h[nn] = val;
    int c = nn;
    int p = nn / 2;
    while(p >= 1 && h[c] > h[p])
    {
        swap(h[c], h[p]);
        c = p;
        p = c / 2;
    }
}

int main()
{
    f>>n>>x>>l;
    for(int i = 1; i <= n; ++ i)
    {
        f>>dist>>lana;
        if(x >= dist)
        {
            int ok = 0;
            long long val = x - dist;
           // if(val % l != 0)
            //    ok = 1;
            val /= l;
            val += ok;
            ++ val;
            graf[val].push_back(lana);
        }
    }

    for(int i = 1; i <= x / l + 1; ++ i)
        sort(graf[i].begin(), graf[i].end(), cmp);

    /*for(int i = 1; i <= n; ++ i)
    {
        for(int j = 0; j < graf[i].size(); ++ j)
            g<<graf[i][j]<<" ";
        g<<'\n';
    }*/

    nn = 1;
    h[1] = graf[1][0];

    for(int i = 2; i <= x / l + 1; ++ i)
    {
        if(!graf[i].empty())
        {
            ++ nn;
            int valoare = graf[i][0];
            percolate(graf[i][0]);
        }
        for(int j = 1; j < graf[i].size() && j < i; ++ j)
        {
            ++ nn;
            int valoare = graf[i][j];
            percolate(graf[i][j]);
            -- nn;
        }
    }

    for(int i = 1; i <= nn; ++ i)
        s += h[i];

    g<<s;

    return 0;
}