Cod sursa(job #1174023)

Utilizator andreiagAndrei Galusca andreiag Data 21 aprilie 2014 17:55:36
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <iostream>
#include <string>
#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 == -1) return -1;
    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>());
/*
    cout << "lana : dist\n";
    for (int i = 0; i < N; i++)
        cout << ferma[i].first << "\t" << ferma[i].second << endl;
    cout << string(32, '=') << '\n';
*/
    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;

        if(root(pas) != -1)
        {
            lana += ferma[i].first;
            // cout << ferma[i].first << '\t' << ferma[i].second << '\n';
            previous[pas] = root(previous[pas] - 1);
        }
    }
    //cout << string(32, '=') << '\n';
    g << lana << '\n';
/*
    for (int i = 0; i < N; i++)
        cout << i << ":\t" << root(i) << '\n';
    cout << string(32, '=') << '\n';
*/
    return 0;
}