Cod sursa(job #1337394)

Utilizator retrogradLucian Bicsi retrograd Data 8 februarie 2015 22:31:15
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream>
#include<algorithm>
#include<cmath>

using namespace std;
typedef int64_t var;

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

const var MAXN = 100001;

var ZI[MAXN];
bool BUSY[MAXN];
var AVAIL[MAXN], WOOL[MAXN], INDEX[MAXN];
var RANK[MAXN], PARENT[MAXN];
var n;

bool cmp(var i, var j) {
    return (WOOL[i] > WOOL[j]);
}

var Find(var ind) {
    if(!PARENT[ind]) {
        return ind;
    } else {
        PARENT[ind] = Find(PARENT[ind]);
        return PARENT[ind];
    }
}

void Union(var r1, var r2) {
    if(RANK[r1] < RANK[r2]) {
        PARENT[r1] = r2;
        AVAIL[r2] = min(AVAIL[r1], AVAIL[r2]);
    } else {

        AVAIL[r1] = min(AVAIL[r1], AVAIL[r2]);
        PARENT[r2] = r1;
        if(RANK[r1] == RANK[r2]) {
            RANK[r1] ++;
        }
    }

}

int main() {
    var x, l, d;
    var total = 0;
    fin>>n>>x>>l;
    for(var i=1; i<=n; i++) {
        fin>>d>>WOOL[i];
        if(d > x) ZI[i] = 0;
        else
            ZI[i] = floor((x-d)/l) + 1;
        AVAIL[i] = i;
        INDEX[i] = i;
    }

    sort(INDEX+1, INDEX+n+1, cmp);

    for(var i=1; i<=n; i++) {
        var &ind = INDEX[i];

        if(ZI[ind] <= 0) continue;

        var day = AVAIL[Find(ZI[ind])];
        if(AVAIL[day]) {
            total += WOOL[ind];
            //BUSY[AVAIL[day]] = 1;
            Union(day, Find(day-1));
        }
    }

    fout<<total;

    return 0;
}