Cod sursa(job #1138699)

Utilizator gedicaAlpaca Gedit gedica Data 10 martie 2014 14:39:25
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;

long long co[nmax+1], ca[nmax+1];

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

deque <long long> deq;

int main()
{
    int n, s, t;
    in >> n >> s >> t;

    for( int i=0; i<n; ++i )
    {
        in >> co[i] >> ca[i];
    }
    long long suma = 0;

    deq.push_back( 0 );
    suma += ca[0]*co[0];

    for( int i=1; i<n; i++)
        {
            while(!deq.empty() && co[i] < co[ deq.back() ]+s*( i-deq.back( ) ) )
            {
                deq.pop_back( );
            }

        deq.push_back( i );
        while( i-deq.front() > t ) {
            deq.pop_front();
        }
        suma += co[ deq.front() ] * ca[i] + ca[i]*s*( i-deq.front() );
    }

    out << suma << '\n';

    return 0;
}