Cod sursa(job #726356)

Utilizator danalex97Dan H Alexandru danalex97 Data 27 martie 2012 10:28:32
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
using namespace std;

ifstream F("lupu.in");
ofstream G("lupu.out");

inline void close_files()
{ F.close(); G.close(); }

#define Nmax 100011

int P[Nmax];
int D[Nmax];
int X,v,V,N;
long long S;

void cobor(int i)
{
	int p=i;
	while ( ( P[i]<P[2*p] && 2*p<=N ) || ( P[i]<P[2*p+1] && 2*p+1<=N ) )
	{
		p=p*2+1;
		if ( P[i]<P[p-1] )
			--p;
		swap(P[i],P[p]);
		swap(D[i],D[p]);
	}
}

void out(int i)
{
	swap(P[1],P[N]);
	swap(D[1],D[N]);
	--N;
	cobor(1);
}

int poz(int st,int dr)
{
	int xst=0,xdr=-1;
	while (st<dr)
		if (P[st]>P[dr])
			st+=xst,dr+=xdr;
		else
		{
			swap(P[st],P[dr]);
			swap(D[st],D[dr]);
			xst=1-xst,xdr=-1-xdr;
			st+=xst,dr+=xdr;
		}
	return st;
}

void urcare(int N, int k) 
{
	int p=P[k];
	int p2=D[k];
	while ( (k>1) && (p>P[k/2]) )  
	{
		P[k]=P[k/2];
		D[k]=D[k/2];
		k=k/2;
	}
   P[k]=p;
   D[k]=p2;
}

void quick(int st,int dr)
{
	int p=poz(st,dr);
	if (p-1>st)
		quick(st,p-1);
	if (p+1<dr)
		quick(p+1,dr);
}

int main()
{
	F>>N>>X>>v;
	for (int i=1; i<=N ;++i)
		F>>D[i]>>P[i],urcare(i,i);
	
	for (int i=1; N>0 ;++i)
	{
		while ( D[1]+V>X && N>0 )
			out(1);
		if ( N>0 )
		{
			S+=P[1];
			out(1);
		}
		V+=v;
	}
	
	G<<S<<'\n';
	
	close_files();
	return 0;
}