Pagini recente » Cod sursa (job #432470) | Cod sursa (job #1587097) | Cod sursa (job #1294262) | Cod sursa (job #2704077) | Cod sursa (job #1173650)
#include <fstream>
#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 != 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>());
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-1;
if(root(pas) != -1)
{
lana += ferma[i].first;
previous[pas] = previous[pas] - 1;
}
}
g << lana << '\n';
return 0;
}