Cod sursa(job #765417)

Utilizator deneoAdrian Craciun deneo Data 7 iulie 2012 16:04:06
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

#define MAXN 110000

vector<pair<int,int> > v(MAXN);

int arb[MAXN * 100];

int getArb(int a) {
    if (arb[a] == a)
        return a;
    arb[a] = getArb(arb[a]);
    return arb[a];
}

void uneste(int a, int b) {
    arb[a] = arb[b];
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first > b.first;
}

int n, x, l, sol;

int main() {
    int a, t, tmax = 0, i;
    fin >> n >> x >> l;
    for (i = 1; i <= n; ++i) {
        fin >> t >> a;
        v[i].second = (x - t) / l + 1;
        v[i].first = a;
        if (v[i].second > tmax)
            tmax = v[i].second;
    }
    sort (v.begin() + 1, v.begin() + n + 1, cmp);
    //cerr << "v[1]: " << tmax << "\n";
    for(i = 1; i <= tmax; ++i) {
        arb[i] = i;
    }
    for (i = 1; i <= n; ++i) { 
        //cerr << "NEW I: " << v[i].second << "\n";
        //cerr << arb[0] << " " << arb[1] << " " << arb[0] << "\n";
        if (getArb(v[i].second) != 0) {
          // cerr << "v[i]: " << v[i].first << " arb: " << getArb(v[i].second) << "\n";
            sol += v[i].first;
           // cerr << getArb(v[i].second) << "\n";
            uneste(getArb(v[i].second), getArb(v[i].second) - 1);
           // cerr << "OK";
        }
    }
    fout << sol << "\n";
    return 0;
}