Cod sursa(job #399444)

Utilizator AstronothingIulia Comsa Astronothing Data 20 februarie 2010 15:01:58
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <iostream>
#include <deque>

using namespace std;

int main()
{
    ifstream f("branza.in");
    ofstream f2("branza.out");
    int n,t,s;
    long long cost[100001];
    long long cant[100001];
    f>>n>>s>>t;
    for(int i=0; i<n; ++i)
        f>>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());
    }

    f2<<suma;

    return 0;
}