Cod sursa(job #2306172)

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

using namespace std;
const int NMAX=100000;
int v[NMAX+1],dq[NMAX+1];
int main()
{
    int dr,st,n,s,t,i,kg,p,sum;
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d %d %d",&n,&s,&t);
    sum=0,st=0,dr=-1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        scanf("%d",&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("%d",sum);
    return 0;
}