Cod sursa(job #2287674)

Utilizator andrei20003Ionescu Andrei andrei20003 Data 22 noiembrie 2018 12:11:59
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.53 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);
    t++;
    for (i=0;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;
}