Cod sursa(job #2412009)

Utilizator bluestorm57Vasile T bluestorm57 Data 21 aprilie 2019 15:50:32
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>

using namespace std;

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

typedef long long int ll;
const int Nmax = 100005;
ll cant, cost[Nmax], best[Nmax];
ll suma;
ll 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;
}