Pagini recente » Cod sursa (job #373580) | Cod sursa (job #784144) | Cod sursa (job #916239) | Cod sursa (job #898299) | Cod sursa (job #562229)
Cod sursa(job #562229)
# include <cstdio>
# include <deque>
typedef long long ll ;
const char *FIN = "branza.in", *FOU = "branza.out" ;
const int MAX = 1000005 ;
std :: deque < ll > Q ;
ll C[MAX] ;
ll N, S, T, P, sol ;
int main ( void ) {
freopen ( FIN, "r", stdin ) ;
scanf ( "%lld %lld %lld", &N, &S, &T ) ;
for ( int i = 1; i <= N; ++i ) {
scanf ( "%lld %lld", C + i, &P ) ;
if ( !Q.empty () && i - Q.front () > T )
Q.pop_front () ;
for ( ; !Q.empty () && C[i] <= C[Q.back()] + S * ( i - Q.back () ) ; Q.pop_back () ) ;
Q.push_back ( i ) ;
sol += ( C[Q.front()] + S * ( i - Q.front () ) ) * P ;
}
fprintf ( fopen ( FOU, "w" ) , "%lld", sol ) ;
}