Cod sursa(job #1804328)

Utilizator Burbon13Burbon13 Burbon13 Data 12 noiembrie 2016 14:27:21
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
#include <iostream>

using namespace std;

const int nmx = 100002;

int n,s,t;
long long c[nmx],p[nmx];
long long dp[nmx];

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)
    {
        dp[i] = dp[i-1] + c[i] * p[i];
        for(int j = i - 1; j >= 1 && j >= i - t; --j)
            dp[i] = min(dp[i],dp[i-1] + c[j] * p[i] + s * (i - j) * p[i]);
    }
}

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

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