Cod sursa(job #1138668)

Utilizator felixiPuscasu Felix felixi Data 10 martie 2014 13:48:45
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <iostream>
#include <deque>

using namespace std;

int main()
{
    ifstream in("branza.in");
    ofstream out("branza.out");
    int n,t,s;
    long long cost[100001], cant[100001];
    in >> n >> s >> t;
    for( int i=0; i<n; i++ ) {
        in >> cost[i] >> cant[i];
    }
    long long suma = 0;
    deque<long long> d;

    d.push_back(0);
    suma += cant[0]*cost[0];

    for( int i=1; 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();
        }
        suma += cost[ d.front() ] * cant[i] + cant[i]*s*( i-d.front() );
    }

    out << suma << '\n';

    return 0;
}