Cod sursa(job #2306173)

Utilizator Vladi.BarasBaras Nicholas Vladimir Laurentiu Vladi.Baras Data 21 decembrie 2018 18:28:35
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX=100000;
long long v[NMAX+1],dq[NMAX+1];
int main()
{
    long long dr,st,n,s,t,i,kg,p,sum;
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%lld %lld %lld",&n,&s,&t);
    sum=0,st=0,dr=-1;
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&v[i]);
        scanf("%lld",&p);
        if(dq[st]==i-(t+1))
        {
            ++st;
        }
        while(st<=dr&&v[i]<=(v[dq[dr]]+(i-dq[dr])*s))
        {
            --dr;
        }
        dq[++dr]=i;
        sum+=p*(v[dq[st]]+(i-dq[st])*s);
    }
    printf("%lld",sum);
    return 0;
}