Cod sursa(job #2500439)

Utilizator Iulia25Hosu Iulia Iulia25 Data 27 noiembrie 2019 22:50:03
Problema Lupul Urias si Rau Scor 24
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

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

pair <int, int> a[100005];

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

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

bool ok(int dist)	{
  int pas = (x - dist) / l;
	int 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);
  for (int i = n; i; --i)	{
    if (ok(a[i].second))	 {
			ans += a[i].first;
    }
  }
  fout << ans;
  return 0;
}