Cod sursa(job #2293024)

Utilizator daniela12Sandu Daniela Teodora daniela12 Data 30 noiembrie 2018 13:59:32
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");

//x->distanta max la care lupul poate alege oi
//l->distanta cu care se muta toate oile dupa fiecare alegere
int n, x, l;
vector<pair<int,int>> v;
multiset <int> s;
void citire()
{
	f >> n >> x >> l;
	int i;
	v.resize(n + 3);
	for (i = 0; i <n; i++)
	{
		f >> v[i].first >> v[i].second;
	}
	f.close();
}
int main()
{
	citire();
	sort(v.begin(), v.begin() + n);
	int i;
	/*for (i = 0; i <= n; i++)
		g << v[i].first << " ";*/
	int q = x % l;
	int nr = 0;
	i = 0;
	while (i <= n && v[i].first<=q)
	{
		s.insert(-v[i].second);
		i++;
	}
	long long int suma = 0;
	if (s.size())
	{
		suma += (*s.begin());
		s.erase((s.begin()));
	}
	nr = i;
	int j = 1; 
	for (i = nr; i <n && v[i].first <= x; i++)
	{
		if (v[i].first <= q + l * j && v[i].first > q + l * (j - 1))	//este in interval de l
		{
			s.insert(-v[i].second);
		}
		else //trec la un nou interval nevid
		{
			while (s.size() && v[i].first > q + l * j)
			{
				suma += (*s.begin());
				s.erase((s.begin()));
				j++;
			}
			if ((v[i].first - q) % l == 0)
			{
				j = (v[i].first - q) / l;
			}
			else
				j = (v[i].first - q) / l + 1;
			s.insert(-v[i].second);
		}
	}
	if (s.size()) //adaug maximul la suma
	{
		suma += (*s.begin());
		s.erase((s.begin()));
	}
	g << -suma << "\n";
	g.close();
	return 0;
}