Cod sursa(job #3170787)

Utilizator cosmin_mihaiDumitru Cosmin cosmin_mihai Data 18 noiembrie 2023 09:54:32
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream>
#include<deque>
#include<vector>
using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

deque<int> zile;
vector<int> branza,costuri;
int main(){
    int n,s,t;
    long long cost=0;
    fin >> n >> s >> t;
    t++;
    branza.resize(n+2);
    costuri.resize(n+2);
    for (int i = 0; i < n;i++){
        int cantitate;
        fin >> costuri[i] >> cantitate;
        if(!zile.empty() && zile.front()==i-t){
            zile.pop_front();
        }
        while(!zile.empty() && costuri[i] <= costuri[zile.back()]+(i-zile.back())*s){// ma asigur ca nu produc branza mai scumpa decat daca as fi depozitat(cost prducere zii anterioara + zile*costDepozitare)
            zile.pop_back();
        }   
        zile.push_back(i);
        cost += (long long)  cantitate * (costuri[zile.front()]+(i-zile.front())*s);
    }

    fout << cost;
    
    return 0;
}