Cod sursa(job #2500437)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 27 noiembrie 2019 22:33:36
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <cstdio>
#include <deque>
using namespace std;
const int NMAX = 100005;
long long c[NMAX];
long long p[NMAX];
deque <long long> dq;

int main() {
    long long n, s, t;
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &s, &t);
    long long sol = 0;
    for(long long i = 1; i <= n; i++) {
        scanf("%lld%lld", &c[i], &p[i]);
        while(!dq.empty() && c[dq.back()] + (i - dq.back()) * s >= c[i]) {
            dq.pop_back();
        }
        while(!dq.empty() && i - dq.front() > t) {
            dq.pop_front();
        }
        dq.push_back(i);
        sol += p[i] * (c[dq.front()] + (i - dq.front()) * s);
    }
    printf("%lld\n", sol);
    return 0;
}