Cod sursa(job #1535334)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 24 noiembrie 2015 17:27:57
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");

long long int cost[100100], cerere[1001000], n, i, s, t, sum;
deque<int> minim;

int main()
{
    fin>>n>>s>>t;

    for (i = 1 ; i <= n ; i++) {
        fin>>cost[i];
        fin>>cerere[i];
    }

    for (i = 1 ; i <= n ; i++) {
        while (minim.size() > 0 && (cost[minim.back()] + (i - minim.back()) * s ) > cost[i]) {
            minim.pop_back();
        }
        minim.push_back(i);

        while (minim.front() < i - t) {
            minim.pop_front();
        }

        sum += cerere[i] * ( cost[minim.front()] + (i - minim.front()) * s );
    }

    fout<<sum;

    return 0;
}