Cod sursa(job #2889025)

Utilizator Andoss1710Balanica Andrei Andoss1710 Data 12 aprilie 2022 04:54:10
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

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

}