Cod sursa(job #2732419)

Utilizator AndreeaCreitaCreita Andreea AndreeaCreita Data 28 martie 2021 22:43:14
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
# include <fstream>
# include <deque>
# include <algorithm>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
deque <int> deq;
long long i,j,n,m,S,T;
long long c[100005], p[100005];
long long total;
int main ()
{
    fin>>n>>S>>T;

    for (i=1; i<=n; ++i)
    {
        fin>>c[i]>>p[i];
        while (! deq.empty() && c[i]<=c[deq.back()]+S*(i-deq.back()))
             deq.pop_back();

        deq.push_back(i);
        if (deq.front()<i-T) deq.pop_front();
        total+=(p[i]*c[deq.front()]+S*p[i]*(i-deq.front()));
    }
    fout<<total<<"\n";
    return 0;
}