Pagini recente » Cod sursa (job #3020936) | Cod sursa (job #2056305) | Cod sursa (job #280128) | Cod sursa (job #175819) | Cod sursa (job #1337394)
#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;
}