Pagini recente » Cod sursa (job #3160813) | Cod sursa (job #1763452) | Cod sursa (job #2961319) | Cod sursa (job #2064256) | Cod sursa (job #1174023)
#include <fstream>
#include <iostream>
#include <string>
#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 == -1) return -1;
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>());
/*
cout << "lana : dist\n";
for (int i = 0; i < N; i++)
cout << ferma[i].first << "\t" << ferma[i].second << endl;
cout << string(32, '=') << '\n';
*/
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;
if(root(pas) != -1)
{
lana += ferma[i].first;
// cout << ferma[i].first << '\t' << ferma[i].second << '\n';
previous[pas] = root(previous[pas] - 1);
}
}
//cout << string(32, '=') << '\n';
g << lana << '\n';
/*
for (int i = 0; i < N; i++)
cout << i << ":\t" << root(i) << '\n';
cout << string(32, '=') << '\n';
*/
return 0;
}