Cod sursa(job #1804406)

Utilizator Burbon13Burbon13 Burbon13 Data 12 noiembrie 2016 15:36:19
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <iostream>
#include <deque>

using namespace std;

const int nmx = 100002;

int n,s,t;
long long c[nmx],p[nmx];
long long dp[nmx];
deque <pair<int,int> > dq;

void citire()
{
    scanf("%d %d %d", &n, &s, &t);
    for(int i = 1; i <= n; ++i)
        scanf("%lld %lld", &c[i], &p[i]);
}

void dinamica()
{
    for(int i = 1; i <= n; ++i)
    {
        while(not dq.empty() && dq.back().second + (i-dq.back().first) * s > c[i])
            dq.pop_back();

        dq.push_back(make_pair(i,c[i]));

        while(not dq.empty() && dq.front().first < i - t)
            dq.pop_front();

        dp[i] = dp[i-1] + min(c[i]*p[i],p[i]*dq.front().second+(i-dq.front().first)*s*p[i]);

    }
}

void afish()
{
    printf("%lld\n", dp[n]);
}

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    citire();
    dinamica();
    afish();
    return 0;
}