Cod sursa(job #2155263)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 7 martie 2018 18:58:33
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream in ("branza.in");
ofstream out ("branza.out");
long long n,s,t,x,cost[100001],cant[100001];
deque<long long> w;
long long sum,v[100001];
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 (1LL*cost[i],cost[w.front()]+s*(i-w.front()) ) * cant[i];
        }
        else {
            sum +=  1LL*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;
}