Cod sursa(job #2887675)

Utilizator DragosG12Ghinea Dragos DragosG12 Data 9 aprilie 2022 23:40:44
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<fstream>
#include<deque>
using namespace std;

int costuri[100005];
int cantitate[100005];

int n,s,t;

deque<int> profitabil;

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

    fin>>n>>s>>t;

    long long cost=0;
    for(int i=0;i<n;i++){
        fin>>costuri[i]>>cantitate[i];

        while(!profitabil.empty() && i-profitabil.front()>t){
            profitabil.pop_front();
        }

        while(!profitabil.empty() && costuri[profitabil.back()]*cantitate[i] + s*(i-profitabil.back())*cantitate[i] > costuri[i]*cantitate[i]){
            profitabil.pop_back();
        }

        profitabil.push_back(i);

        cost+=costuri[profitabil.front()]*cantitate[i]+s*(i-profitabil.front())*cantitate[i];
    }

    fout<<cost;

    fout.close();
    fin.close();

    return 0;
}