Cod sursa(job #2719354)

Utilizator BriannaBrianna Stan Brianna Data 9 martie 2021 19:41:11
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream in("branza.in");
ofstream out("cost.out");
static int c[100002];
deque<int> dq;
int main() {
    int n,t,s;
    long long cost=0;
    in>>n>>s>>t;
    t++;
    for(int i=0;i<n;i++) {
        int p;
        in >> c[i] >> p;
        if (!dq.empty() && dq.front() == i - t) {
            dq.pop_front();
        }
        while (!dq.empty() && c[i] <= c[dq.back()] + s * (i - dq.back()))
            dq.pop_back();
        dq.push_back(i);
        cost += (long long) p*(c[dq.front()] + s * (i - dq.front()));
    }
    out<<cost;
    return 0;
}