Cod sursa(job #1503205)

Utilizator gedicaAlpaca Gedit gedica Data 15 octombrie 2015 18:35:06
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <deque>

using namespace std;

const int NMAX= 100000;

ifstream in( "branza.in" );
ofstream out( "branza.out" );

deque <long long> d;

long long cost[NMAX+1], cant[NMAX+1];

int main(  )
{
    long long N, S, T;
    in >> N >> S >> T;

    for( int i= 1; i<=N; ++i )
    {
        in >> cost[i] >> cant[i];
    }
    long long Ans = 0;

    d.push_back( 1 );
    Ans += cant[1]*cost[1];

    for( int i= 2; i<=N; ++i )
    {
        while( !d.empty() && cost[i]<cost[ d.back() ] + S*( i-d.back( ) ) )
        {
            d.pop_back(  );
        }

        d.push_back( i );

        while( i-d.front() > T )
        {
            d.pop_front();
        }

        Ans += cost[ d.front() ] * cant[i] + cant[i]*S*( i-d.front() );
    }

    out << Ans << '\n';
    return 0;
}