Cod sursa(job #1376428)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 5 martie 2015 17:22:26
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.59 kb
#include<fstream>
#include<algorithm>
#include<vector>

#define NMAX 100001

using namespace std;

struct SHEEP{int wool, time;};
struct HEAP
{
	vector<int> heap;

	HEAP()
	{
		heap.push_back(0);
	}
	
	void upHeap(int pos)
	{
		int val=heap[pos];
		int father=pos/2;
		while(father && heap[father]<val)
		{
			heap[pos]=heap[father];
			pos=father;
			father=pos/2;
		}
		heap[pos]=val;		
	}

	void push(int val)
	{
		heap.push_back(val);
		upHeap(heap.size()-1);
	}
	
	void downHeap(int pos)
	{
		int son=pos*2;
		int val=heap[pos];
		while(son<=(heap.size()-1))
		{
			if(son<(heap.size()-1))
				if(heap[son+1]>heap[son])
					son++;
			if(heap[son]>val)
				break;
			heap[pos]=heap[son];
			pos=son;
			son=pos*2;
		}
		heap[pos]=val;
	}

	int pop_max()
	{
		int val=heap[1];
		heap[1]=heap.back();
		heap.pop_back();
		downHeap(1);
		return val;
	}
};

bool compSHEEP(SHEEP a, SHEEP b)
{
	if(a.time<b.time)
		return 1;
	return 0;
}

SHEEP shp[NMAX];

int main()
{
	int n, x, l;
	int i;
	int initial_distance;
	long long total=0;
	int nsh;
	int tmax=0;
	HEAP h;
	ifstream f("lupu.in");
	f>>n>>x>>l;
	for(i=1; i<=n ;i++)
	{
		f>>initial_distance>>shp[i].wool;
		shp[i].time=(x-initial_distance)/l;
		if(shp[i].time>tmax)
			tmax=shp[i].time;
	}
	f.close();
	sort(shp+1, shp+n+1, compSHEEP);
	nsh=n;
	for(i=tmax; i>=0; i--)
	{
		while(shp[nsh].time==i && nsh)
		{
			h.push(shp[nsh].wool);
			nsh--;
		}
		total=total+(long long)h.pop_max();
	}
	ofstream g("lupu.out");
	g<<total<<'\n';
	g.close();
	return 0;
}