Cod sursa(job #2610337)

Utilizator stefanlupoi1Lupoi Stefan stefanlupoi1 Data 4 mai 2020 19:01:37
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <cstdio>

using namespace std;

int d[100002],v[100002];

int main()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    int st,dr,n,t,s,c;
    long long pr=0;
    scanf("%d%d%d",&n,&s,&t);
    st=0;
    dr=-1;
    t++;
    for(int i=0;i<n;i++){
        scanf("%d%d",&v[i],&c);
        if(st<=dr&&d[st]==i-t){
            st++;
        }
        while(st<=dr&&v[d[dr]]+(i-d[dr])*s>=v[i]){
            dr--;
        }
        d[++dr]=i;
        pr+=(long long)c*((long long)v[d[st]]+(long long)(i-d[st])*(long long)s);
    }
    printf("%lld",pr);
    return 0;
}