Cod sursa(job #3170821)

Utilizator DequeDeea Parascan Deque Data 18 noiembrie 2023 10:26:32
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int main()
{
    int n,s,t;
    long long cost_total=0;
    f >>n>>s>>t;
    t++;
    deque <long long> dq;
    vector <int> cost(n+1);
    
    for(int i=0;i<n;i++){
        int cantitate;
        f>>cost[i]>>cantitate;
        
        while(!dq.empty() && dq.front()==i-t)
            dq.pop_front();
            
        while(!dq.empty() && cost[i]<=cost[dq.back()] + (i-dq.back())*s)
            dq.pop_back();
        
        dq.push_back(i);
        cost_total=cantitate * ( cost[dq.front()] + ( i - dq.front() ) * s );
    }
    
    g <<cost_total;
    
    return 0;
}