Cod sursa(job #2155253)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 7 martie 2018 18:54:36
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream in ("branza.in");
ofstream out ("branza.out");
int n,s,t,x,sum,cost[100001],cant[100001],v[100001];
deque<int> w;
int main (void) {
    in >> n >> s >> t;
    for (int i = 1; i <= n; i ++) {
        in >> cost[i] >> cant[i];
    }
    for (int i = 1; i <= n; i ++) {
        if (w.empty() == 0) {
            sum += min (cost[i],cost[w.front()]+s*(i-w.front()) ) * cant[i];
        }
        else {
            sum +=  cost[i] * cant[i];
        }
        x = cost[i] + s*(n-i+1);
        while (w.empty() == 0 && x < v[w.back()]) {
            w.pop_back();
        }
        w.push_back(i);
        v[i] = x;
        if (w.front() < i-t) {
            w.pop_front();
        }
    }
    out << sum;
    return 0;
}