Cod sursa(job #3039607)

Utilizator stefanchpStefan Chiper stefanchp Data 28 martie 2023 18:28:03
Problema Lupul Urias si Rau Scor 32
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>
using namespace std;

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

int n, x, l;
set <int, greater<int>> s;
struct oaie 
{
	int dist, lana;
} a[100005];

inline bool cmp(oaie x, oaie y)
{
	return x.dist < y.dist;
}

int main()
{
	int d, y;
	fin >> n >> x >> l;
	for (int i = 1; i <= n; i++)
	{
		fin >> d >> y;
		if (d > x) continue;
		else a[i].dist = d, a[i].lana = y;
	}
	fin.close();

	sort(a + 1, a + n + 1, cmp);
	int pas_max = (x - a[1].dist) / l + 1;
	int pas_curent = pas_max;
	long long sol = 0;
	int oaie_curenta = 1;
	while (pas_curent >= 1)
	{
		for (int i = oaie_curenta; i <= n; i++)
		{
			int pas_oaie = (x - a[i].dist) / l + 1;
			if (pas_oaie == pas_curent)
				s.insert(a[i].lana);

			if (pas_oaie < pas_curent)
			{
				oaie_curenta = i;
				break;
			}
		}
		if (!s.empty())
		{
			sol += 1LL * (*s.begin());
			s.erase(s.begin());
		}
		pas_curent--;
	}
	fout << sol;
	fout.close();
	return 0;
}