Cod sursa(job #793572)

Utilizator vendettaSalajan Razvan vendetta Data 3 octombrie 2012 15:50:26
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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 (1LL<<61)
#define ll long long

ll n, S, T, C[nmax], P[nmax], dp[nmax];
deque<ll> dq;

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;
        int poz = 0;
        ll Min = 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));
            if ( Min > C[j]/S-i -1LL*j) {
                Min = C[j]/S-i -1LL*j;
                poz = j;
            }

        }
        dp[i] = P[i] * C[poz] + S * P[i] * 1LL*(i-poz);
        dp[i] += dp[i-1];
    }

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

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}