Cod sursa(job #2803054)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 19 noiembrie 2021 12:37:43
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <deque>
#define ll long long

using namespace std;

ifstream cin("branza.in");
ofstream cout("branza.out");

const int NMAX = 1e5;
long long c[NMAX + 1], p[NMAX + 1], ans, n, s, t;
deque <int> dq;

void read(){

    cin >> n >> s >> t;
    for(int i = 1; i <= n; i++)
        cin >> c[i] >> p[i];

}

void solve(){

    for(int i = 1; i <= n; i++){

        while(!dq.empty() && c[i] <= c[dq.back()] + s * (i - dq.back()))  // daca branza curenta este mai buna decat ultima + costul zilelor de cand e depozitata
            dq.pop_back();

        dq.push_back(i);

        while(!dq.empty() && dq.front() < i - t) // scot branza stricata, care a fost depozitata de mai mult de t saptamani
            dq.pop_front();    

        ans += p[i] * (c[dq.front()] + s * (i - dq.front())); // adaug cantiatea * (cea_mai_buna_branza + costul pentru depozitare de i - dq.front() zile)

    }

    cout << ans;
  
}

int main(){

    read();
    solve();

}