Cod sursa(job #1173646)

Utilizator andreiagAndrei Galusca andreiag Data 20 aprilie 2014 14:24:40
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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, D, A;
    f >> N >> X >> L;
    for (int i = 0; i < N; i++)
    {
        f >> D >> A;
        if (D > X) { --i; --N; }
        else ferma[i] = make_pair(A, D);
    }

    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++)
    {
        int pas = (X - ferma[i].second) / L;
        if (pas >= N) pas = N-1;

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

    return 0;
}