Cod sursa(job #562229)

Utilizator SpiderManSimoiu Robert SpiderMan Data 22 martie 2011 17:35:18
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
# 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 ) ;
}