Pagini recente » Cod sursa (job #3161045) | Cod sursa (job #3168058) | Cod sursa (job #1886020) | Cod sursa (job #429925) | Cod sursa (job #383246)
Cod sursa(job #383246)
#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 ;
inline void stanga ( int i )
{
if ( dq[st]-i == 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 ) ;
++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 ;
}