Pagini recente » Cod sursa (job #2169475) | Cod sursa (job #283830) | Cod sursa (job #578881) | Cod sursa (job #2817371) | Cod sursa (job #765414)
Cod sursa(job #765414)
#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 * 10];
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] = 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;
}