Cod sursa(job #726401)

Utilizator danalex97Dan H Alexandru danalex97 Data 27 martie 2012 10:55:16
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 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

typedef int Heap[100001];

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

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

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);
}

void cobor(Heap a, Heap b, int n , int k)
{
	int p;
	p=1;
	while (p)
	{
		p=0;
        if ( 2*k<=n ) 
		{
            p=2*k; 
            if ( (2*k+1<=n) && (a[2*k+1]>a[2*k]) ) 
                p++; 
            if (a[p] <= a[k])
                p=0;
        }
        if ( p>0 )
		{
            swap(a[k],a[p]); 
            swap(b[k],b[p]); 
            k=p;
        }
	}
}

void urcare(Heap a, Heap b, int n, int k) 
{
	int p=a[k];
	int p2=b[k];
	while ( (k>1) && (p>a[k/2]) )  
	{
		a[k]=a[k/2];
		b[k]=b[k/2];
		k=k/2;
	}
   a[k]=p;
   b[k]=p2;
}

void elimin(Heap a, Heap b, int& n, int k) 
{
    a[k]=a[n]; 
    b[k]=b[n]; 
    --n; 
    if ( (k>1) && (a[k]>a[k/2]) ) 
        urcare(a,b,n,k); 
	else                          
        cobor(a,b,n,k);
}

void insert(Heap a, Heap b, int& n, int val ,int val2) 
{
    a[++n]=val;
    b[n]=val2;
    urcare(a, b, n, n);
}

int main()
{
	F>>N>>X>>v;
	for (int i=1; i<=N ;++i)
		F>>B[i]>>A[i];
	quick(1,N);
	
	int co=0;
	while (V<=X)
		V+=v;
	int j=0;	
	
	for (int i=1; V>0 ;++i)
	{
		V-=v;
		
		while ( B[j+1]+V<=X && j<=N )
			++j,insert(P,D,co,A[j],B[j]);
		
		if ( co>0 )
			S+=P[1],elimin(P,D,co,1);
	}
	
	G<<S<<'\n';
	
	close_files();
	return 0;
}