Cod sursa(job #2500450)

Utilizator Iulia25Hosu Iulia Iulia25 Data 27 noiembrie 2019 23:02:48
Problema Lupul Urias si Rau Scor 48
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("lupu.in");
ofstream fout ("lupu.out");

long long tata[100005];
long long ans, n, x, l;
bool b[100005];

pair <long long, long long> a[100005];

long long find_tata(long long nod)	 {
  while (tata[nod] >= 0)
		nod = tata[nod];
	return nod;
}

void set_tata(long long nod, long long t)	 {
	while (tata[nod] >= 0)	{
		long long aux = nod;
		nod = tata[nod];
		tata[aux] = t;
	}
}

bool cmp(pair <long long, long long> _x, pair <long long, long long> _y)	{
	return (_x.first > _y.first || _x.first == _y.first && _x.second < _y.second);
}

bool ok(long long dist)	{
  long long pas = (x - dist) / l;
  if (pas < 0)
		return false;
	long long t = find_tata(pas);
	set_tata(pas, t);
	if (b[t])
		return false;
	tata[t] = t - 1;
	if (t == 1)
		tata[t] = -1;
	b[t] = true;
	return true;
}

int main()	{
  fin >> n >> x >> l;
  tata[0] = -1;
  for (int i = 1; i <= n; ++i)	{
		fin >> a[i].second >> a[i].first;
		tata[i] = -1;
	}
	sort (a + 1, a + n + 1, cmp);
  for (int i = 1; i <= n; ++i)	{
    if (ok(a[i].second))	 {
			ans += a[i].first;
    }
  }
  fout << ans;
  return 0;
}