Cod sursa(job #2176041)

Utilizator clokerulLazureanu George clokerul Data 16 martie 2018 20:34:37
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.5 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
long long d[100001],v[100001],n,k,s;
int main()
{
    in >> n >> s >> k;
    long long i,c,st=1,dr=0,suma=0;
    for (i=1;i<=n;++i)
    {
        in >> v[i] >> c;
        if (d[st]==i-k)
            st++;
        while (st<=dr && v[i]<=v[d[dr]]+s*(i-d[dr]))
            dr--;
        d[++dr]=i;
        suma+=c*(v[d[st]]+s*(i-d[st]));
    }
    out << suma;
    return 0;
}