Pagini recente » Cod sursa (job #1926534) | Cod sursa (job #1844363) | Cod sursa (job #1889253) | Cod sursa (job #182565) | Cod sursa (job #1173646)
#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, D, A;
f >> N >> X >> L;
for (int i = 0; i < N; i++)
{
f >> D >> A;
if (D > X) { --i; --N; }
else ferma[i] = make_pair(A, D);
}
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++)
{
int pas = (X - ferma[i].second) / L;
if (pas >= N) pas = N-1;
if(root(pas) != -1)
{
lana += ferma[i].first;
previous[pas] = pas - 1;
}
}
g << lana << '\n';
return 0;
}