Cod sursa(job #1450745)

Utilizator LegionHagiu Stefan Legion Data 14 iunie 2015 16:29:08
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> lacatipasi[100001];
vector<int> gramada;
int main()
{
	ifstream in("lupu.in");
	ofstream out("lupu.out");
	int i, n, d, k,j, x, y,total=0;
	in >> n;
	in >> d;
	in >> k;
	for (i = 1; i <= n; i++)
	{
		in >> x;
		in >> y;
		if (x > d){ continue; }
		else
		{
			x = d-x;
			if (k == 0)
			{
				lacatipasi[100000].push_back(y);
				continue;
			}
			lacatipasi[min(100000,x / k)].push_back(y);
		}
	}
	for (i = 100000; i >= 0; i--)
	{
		for (j = 0; j < lacatipasi[i].size(); j++)
		{
			gramada.push_back(lacatipasi[i][j]);
			push_heap(gramada.begin(), gramada.end());
		}
		if (gramada.size()>0)
		{
			total += gramada[0];
			pop_heap(gramada.begin(), gramada.end());
			gramada.pop_back();
		}
	}
	out << total;
}