Cod sursa(job #1173650)

Utilizator andreiagAndrei Galusca andreiag Data 20 aprilie 2014 14:53:04
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <algorithm>

using namespace std;
const int Nmax = 100111;
typedef pair<int, int> oaie; // oaie = pair<lana, distanta>
typedef long long ll;

oaie ferma[Nmax];
int previous[Nmax];

int root(int x)
{
    if ((x != previous[x]) && (previous[x] != -1))
        previous[x] = root(previous[x]);

    return previous[x];
}

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

    int N, X, L;
    f >> N >> X >> L;
    for (int i = 0; i < N; i++)
        f >> ferma[i].second >> ferma[i].first;

    for (int i = 0; i <= N; i++)
        previous[i] = i;

    sort(ferma, ferma+N, greater<oaie>());
    
    ll lana = 0;

    for (int i = 0; i < N; i++)
    {
        if (X < ferma[i].second) continue;
        int pas = (X - ferma[i].second) / L;
        if (pas >= N) pas = N-1;

        if(root(pas) != -1)
        {
            lana += ferma[i].first;
            previous[pas] = previous[pas] - 1;
        }
    }
    g << lana << '\n';

    return 0;
}