Cod sursa(job #793563)

Utilizator vendettaSalajan Razvan vendetta Data 3 octombrie 2012 15:35:21
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

#define nmax 100005
#define inf (1<<29)
#define ll long long

int n, S, T, C[nmax], P[nmax], dp[nmax];

void citeste(){

	f >> n >> S >> T;
    for(int i=1; i<=n; ++i){
        f >> C[i] >> P[i];
    }

}

void rezolva(){

    //ideea ar fi : dp[i] = costul minim pentru a acoperi primele i cerinte

    for(int i=1; i<=n; ++i){
        dp[i] = inf;
        for(int j=i; j>=i-T; --j){
            if (j<=0) break;//altfel intra in balarii
            dp[i] = min(dp[i], P[i]*C[j] + S * P[i] * (i-j));
        }
        dp[i] += dp[i-1];
    }

    g << dp[n] << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}