Cod sursa(job #385615)

Utilizator alutzuAlexandru Stoica alutzu Data 23 ianuarie 2010 09:43:54
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>
#include<cstdio>

struct chestie { int c , cump ; } ;

int t , s ;
const int NMAX = 1<<17;

int dq [NMAX];
chestie branza [ NMAX ] ;
int st , dr=0 ;

inline void stanga ( int i )
{
	if ( i - dq[st] > t )
		++ st ;
}

void dreapta ( int i )
{

	while ( st <= dr && ( branza[ i ].c <= ( branza[ dq[dr] ].c + (i-dq[dr])*s) ) )
		--dr;
	dq[++dr]=i;
	
}


int main ( )
{
	freopen ( "branza.in" , "r" , stdin ) ;
	freopen ( "branza.out" , "w" , stdout );
	
	int n ;
	long long S = 0 ;
	int i ;
	scanf ( "%d%d%d" , & n , & s , & t ) ;

	for ( i = 1 ; i <= n ; ++ i ) 
	{
		scanf ( "%d%d" , & branza[i].c , &branza[i].cump ) ;
	}

	st=1;
	for ( i = 1 ; i <= n ; ++ i )
	{
		stanga (i) ;
		dreapta (i) ;
		S += (long long )( branza [ dq[st] ].c  + (i-dq[st])*s ) * branza[i].cump ;
		
	}
	
	printf ( "%lld\n" , S ) ;
	
	
	return 0 ;
}