Pagini recente » Cod sursa (job #1499924) | Cod sursa (job #1458850) | Cod sursa (job #84669) | Cod sursa (job #871308) | Cod sursa (job #2582520)
#include <cstdio>
#include <algorithm>
using namespace std ;
const long long NMAX = 1e5 , INF = 1e18 ;
long long v [ NMAX + 5 ] , data [ NMAX + 5 ] ;
long long dpl [ NMAX + 5 ] , dpr [ NMAX + 5 ] ;
int main ()
{
freopen ( "branza.in" , "r" , stdin ) ;
freopen ( "branza.out" , "w" , stdout ) ;
long long n , s , t , i ;
unsigned long long ans = 0 ;
scanf ( "%lld%lld%lld" , & n , & s , & t ) ;
for ( i = 0 ; i < n ; ++ i )
{
scanf ( "%lld%lld" , & v [ i ] , & data [ i ] ) ;
v [ i ] += s * ( n - i ) ;
}
for ( i = 0 ; i < n ; ++ i )
if ( i % t == 0 )
dpl [ i ] = v [ i ] ;
else
dpl [ i ] = min ( dpl [ i - 1 ] , v [ i ] ) ;
dpr [ n ] = INF ;
for ( i = n - 1 ; i >= 0 ; -- i )
if ( i % t == t - 1 )
dpr [ i ] = v [ i ] ;
else
dpr [ i ] = min ( dpr [ i + 1 ] , v [ i ] ) ;
for ( i = 0 ; i < t ; ++ i )
ans += 1LL * data [ i ] * ( dpl [ i ] - s * ( n - i ) ) ;
for ( i = t ; i < n ; ++ i )
{
long long val = min ( dpr [ i - t ] , dpl [ i ] ) ;
ans += 1LL * data [ i ] * ( val - s * ( n - i ) ) ;
}
printf ( "%llu" , ans ) ;
return 0 ;
}