Cod sursa(job #2729896)

Utilizator MadalinaKopaczMadalina Kopacz MadalinaKopacz Data 25 martie 2021 15:55:18
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

int main(){
    long long n, s, t, p,i,c[N], total = 0;
    deque<int> deq;

    fin >> n >> s >> t; t++;

    for(i = 0; i < n; i++)
        {
        fin >> c[i] >> p;
        if(!deq.empty() && deq.front() == i - t)  deq.pop_front();   ///ignoram prima din secventa
        while(!deq.empty() && c[i] <= c[deq.back()] + s * (i - deq.back())) deq.pop_back();   ///minimizam costurile (costul curent e mai mic decat costul de depozitare+costul din sapt prec
        deq.push_back(i);
        total += (long long)p * (c[deq.front()] + s * (i - deq.front()));   ///adaugam la cheltuielile totale
        }

    fout << total;
}