Cod sursa(job #2071524)

Utilizator cyg_BengaBenga Theodor cyg_Benga Data 20 noiembrie 2017 19:07:26
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include <fstream>

using namespace std;

ifstream in("branza.in");
ofstream out("branza.out");
const int N = 100001;
int d[N],c[N],p[N];

int main()
{
    int n,t,i,j,st,dr,s=0;
    long long ma=0;
    in>>n>>s>>t;
    t++;
    st=0,dr=-1;
    for(i=1;i<=n;i++)
    {
        in>>c[i]>>p[i];

        if (st <= dr && d[st] == i - t)
            st++;

        while(st<=dr && c[i]<=c[d[dr]]+(long long)s*(i-d[dr]))
            dr--;

        d[++dr]=i;
        ma  +=p[i]*(c[d[st]]+(long long)s*(i-d[st]));
    }
    out<<ma;
    return 0;
}