Cod sursa(job #2287672)

Utilizator andrei20003Ionescu Andrei andrei20003 Data 22 noiembrie 2018 12:10:38
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.52 kb
#include <bits/stdc++.h>

using namespace std;

int v[100001],d[100001];

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