Cod sursa(job #2889033)

Utilizator Andoss1710Balanica Andrei Andoss1710 Data 12 aprilie 2022 05:30:24
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

int main()
{
    deque < long long int > branza;
    long long int suma = 0;
    int n, s, t;
    fin>>n>>s>>t;
    long long int cost[n], cant[n];
    for(long long int i = 0; i < n; i++)
        fin>>cost[i]>>cant[i];
    for(long long int i = 0; i < t; i++){
        while(!branza.empty() && cost[i] <= cost[branza.back()] + s * (i-branza.back())){
            branza.pop_back();
        }
        branza.push_back(i);
        suma = suma + cant[i] * (cost[branza.front()] + s * (i - branza.front()));
    }

    for(long long int i = t; i < n; i++){
        if((i - branza.front())-t > 0){
            branza.pop_front();
        }
        while(!branza.empty() && cost[i] <= cost[branza.back()] + s * (i-branza.back())){
            branza.pop_back();
        }
        branza.push_back(i);
        suma = suma + cant[i] * (cost[branza.front()] + s * (i - branza.front()));

    }
    fout<<suma;

    return 0;

}