Cod sursa(job #2732086)

Utilizator andi2000Toader Andi andi2000 Data 28 martie 2021 18:23:51
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

deque<long long> pret_minim;
int c [100010];
int main()
{
    int n, s, t, p;
    long long min = 0;
    f >> n >> s >>t;
    for (int i=0; i<n; i++)
    {
        f >> c[i] >> p;
        if(pret_minim.size()!=0 && pret_minim.front() == i-t)
            pret_minim.pop_front();
        while(pret_minim.size()!=0 && c[i] <= c[pret_minim.back()] + s*(i-pret_minim.back()))
            pret_minim.pop_back();
        pret_minim.push_back(i);
        min += (long long)p * (c[pret_minim.front()]+s*(i-pret_minim.front()));
    }
   g << min;
}