Cod sursa(job #2412005)

Utilizator bluestorm57Vasile T bluestorm57 Data 21 aprilie 2019 15:43:05
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>

using namespace std;

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

const int Nmax = 100005;
int cant, cost[Nmax], best[Nmax];
long long int suma;
int n,s,t, last = -1, first;

int main(){
    int i;
    f >> n >> s >> t;
    for(i = 1; i <= n ; i++){
        f >> cost[i] >> cant;

        if(best[first] == i - t - 1)
            first++;

        while(first <= last && cost[i] <= (cost[best[last]] + (i - best[last]) * s ))
            last--;

        best[++last] = i;

        suma += cant * (cost[best[first]] +  (i - best[first]) * s);
    }

    g << suma;
    return 0;
}