Cod sursa(job #937911)

Utilizator ericptsStavarache Petru Eric ericpts Data 11 aprilie 2013 12:15:33
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <deque>
#include <algorithm>
#include <iostream>

using namespace std;

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

#define pb push_back
#define rm_front(D) while(!D.empty() && D.front() < i - lifetime)D.pop_front()
#define rm_back(D) while(!D.empty() && cost[i] < cost[D.back()] + extra * (i - D.back()))D.pop_back()

const int maxn = 100100;
typedef long long LL;
LL cost[maxn],req[maxn];
LL best[maxn];

deque<int> D;

int main()
{
    LL n,extra,lifetime,i;
    LL now,before;
    in >> n >> extra >> lifetime;
    for(i=1;i<=n;++i)
        in >> cost[i] >> req[i];
    best[1] = cost[1]*req[1];
    D.pb(1);
    for(i=2;i<=n;++i){
        rm_front(D);
        rm_back(D);
        D.pb(i);
        now = cost[i];
        before = cost[D.front()] + extra * (i - D.front());
        best[i] = 1LL*min(now,before) * req[i];
    }
    unsigned long long show = 0;
    for(i=1;i<=n;++i)
        show += best[i];
    out << show << "\n";
    return 0;
}