Cod sursa(job #793755)

Utilizator vendettaSalajan Razvan vendetta Data 3 octombrie 2012 22:39:06
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 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;
int poz[nmax];

void citeste(){

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

}


void preprocesare(){

    //imi selectez o constanta X = n+1; astfel : fie j,k cu j < k => j va fi ales daca c[j] + S * (X-j) < c[k] + * S * (X - k)
    int X = n+1;

    for(int i=1; i<=n; ++i){
        while (!dq.empty() && ( C[dq.back()] + S * 1LL*(X-dq.back()) ) >= (C[i] + S * 1LL*(X-i)) )
            dq.pop_back();
        dq.push_back(i);
        if (dq.size() &&  i - dq.front() > T) dq.pop_front();
        poz[i] = dq.front();
    }

}

void rezolva(){

    //ideea ar fi : dp[i] = costul minim pentru a acoperi primele i cerinte
    //imi preprocesez un cost[i] = costul de la pasul i(mai exact in ce saptamana am sa produc branza de care am nevoie la pasul i)

    preprocesare();

    for(int i=1; i<=n; ++i){
        ll X =  P[i] * C[ poz[i] ] + S * P[i] * 1LL*(i- poz[i] );
        dp[i] = dp[i-1] + X;
    }

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

}

int main(){

    citeste();
    rezolva();

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

    return 0;

}