Cod sursa(job #1492151)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 27 septembrie 2015 08:39:51
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <cstdio>

#define NMAX 100007
#define LL long long

using namespace std;
int n, s, t, dq[NMAX], st = 1, dr = 1;
LL v[NMAX], p, ans;

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