Cod sursa(job #590720)

Utilizator AnteusPatrascoiu Mihai Anteus Data 19 mai 2011 18:32:20
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream.h>
#include <algorithm>
#define N 100005
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
struct oaie { int d,c;	}	v[N];
int n,T,i,H[N],k;
long long sol;

void citire() {
int i,X,L;
fin>>n>>X>>L;	if (!L)		L=1;
for (i=1;i<=n;i++)
{
	fin>>v[i].d>>v[i].c;
	if (v[i].d<=X)		v[i].d=(X-v[i].d)/L;
	else				v[i].d=v[i].c=0;
}
}

int cmp (oaie a, oaie b)
{
	return (a.d>b.d);
}

void upheap(int x) {
	while (x>1 && H[x]>H[x/2])
	{
		swap (H[x], H[x/2]);
		x/=2;
	}
}

void downheap(int x) {
int fiu;
do
{
	fiu=0;
	if (2*x<=k)							fiu=2*x;
	if (2*x+1<=k && H[fiu]<H[fiu+1])	fiu=2*x+1;
	if (H[x]>=H[fiu])					fiu=0;
	
	if (fiu)
	{
		swap (H[x], H[fiu]);
		x=fiu;
	}
}
while (fiu);
}


int main() {
citire();
sort(v+1, v+n+1, cmp);

for (i=1, T=v[1].d;		i<=n && T>=0;	T--)
{
	while (v[i].d>=T && i<=n)
	{
		H[++k]=v[i++].c;
		upheap(k);
	}
	
	sol+=H[1];
	swap (H[1], H[k--]);
	downheap(1);
	if (i>n)	
		i=n;
}

fout<<sol;
return 0;
}