Cod sursa(job #2730248)

Utilizator Virgil993Virgil Turcu Virgil993 Data 25 martie 2021 23:38:57
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include<bits/stdc++.h>
#include<fstream>

using namespace std;
struct sapt
{
    long long pret;
    long long cerere;
}v[100010];

int main()
{



    ifstream in;
    ofstream out;
    in.open("branza.in");
    out.open("branza.out");
    deque <int> deq;
    int n,s,t;
    long long suma_minima;
    in>>n>>s>>t;
    for(int i=0;i<n;i++)
    {
        in>>v[i].pret>>v[i].cerere;
        if(deq.empty())
            deq.push_back(i);
        else
        {
            while(!deq.empty()&&v[i].pret<= v[deq.back()].pret+s*(i-deq.back()))
                deq.pop_back();
            deq.push_back(i);
            if(deq.front()== i-t-1)
                deq.pop_front();
        }
        suma_minima = suma_minima + v[deq.front()].pret*v[i].cerere + s*(i-deq.front())*v[i].cerere;
    }

out<<suma_minima;




    return 0;
}