Cod sursa(job #2007573)

Utilizator antanaAntonia Boca antana Data 3 august 2017 12:44:21
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

#define MAXN 100001

using namespace std;

deque <int> dq;

int n, S, T;
long long d[MAXN], cf[MAXN];

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);

    int i, P, C;

    scanf("%d%d%d", &n, &S, &T);
    for(i=1; i<=n; ++i) {
        scanf("%d%d", &C, &P);
        d[i] = 1LL * C * P;

        while(!dq.empty() && i - dq.front() > T)
            dq.pop_front();
        if(!dq.empty())
            d[i] = min(d[i], 1LL * P * i * S + P * cf[dq.front()]);

        d[i] += d[i-1];
        cf[i] = C - S * i;
        while(!dq.empty() && cf[i] < cf[dq.back()])
            dq.pop_back();
        dq.push_back(i);
    }

    printf("%lld", d[n]);
    return 0;
}