Cod sursa(job #2174240)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 16 martie 2018 11:21:05
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <deque>
#define dimn 100005
#define ll long long

std::ifstream f("branza.in");
std::ofstream g("branza.out");

ll N, S, T;
ll cost[dimn], cant[dimn];
ll prod[dimn];

void citire() {
    f >> N >> S >> T;
    for (ll i=0; i<N; i++)
        f >> cost[i+1] >> cant[i+1];
}
std::deque <ll> dq;
void rezolvare() {
    for (ll i=1; i<=N; i++) {
        while(!dq.empty() && i-T >= dq.front())
            dq.pop_front();
        while(!dq.empty() && cost[dq.back()] - S*dq.back() >= cost[i] - S*i)
            dq.pop_back();
        dq.push_back(i);

        prod[dq.front()] += cant[i];
    }

    ll res = 0;
    ll stoc = 0;
    for (ll i=1; i<=N; i++) {
        res = res + prod[i]*cost[i];
        res = res + stoc*S;
        stoc += (prod[i]-cant[i]);
    }
    g << res;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}