Cod sursa(job #2046211)

Utilizator cip_ionescuCiprian Ionescu cip_ionescu Data 23 octombrie 2017 16:22:02
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#define MAX_N 100000

int price[MAX_N], weight[MAX_N], dp[MAX_N], dw[MAX_N], d[MAX_N];

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

int main()
{
    int n, s, t, st, dr;
    long long S;

    fin >> n >> s >> t;

    st = 1;
    dr = 0;
    S = 0;

    for(int i = 0 ; i < n ; i++){
        fin >> price[i] >> weight[i];

        if(i >= t && d[st] == i - t) st++;

        while(st <= dr && price[i] < dp[dr] + (i - d[dr]) * s) dr--;

        dp[++dr] = price[i];
        d[dr] = i;
        S += (dp[st] + (i - d[st]) * s) * weight[i];
    }
    fout << S;
    return 0;
}