Cod sursa(job #2887948)

Utilizator AncaGAncuta Gava AncaG Data 10 aprilie 2022 14:15:16
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

int main() {
    long long n, s, deposit_weeks, cost[100005] = {}, q_sold, total_cost = 0;

    ifstream fin("branza.in");
    fin >> n >> s >> deposit_weeks;

    deque<long long> index_week;
// practic e important sa-mi dau seama de cand si la ce cost pot sa produc mai mult si implicit sa incep sa depozitez
    for (int week = 1; week <= n; week++) {
        fin >> cost[week] >> q_sold;

 // nu am voie sa am pe coada dubla ramas un index al unei sapt trecute < curent week - deposit_weeks
// ar insemna a s-a depasit termennul de depozitare al branzei
        while (!index_week.empty() &&  week - index_week.front() > deposit_weeks)
            index_week.pop_front();

        
// determin acel break-even point in costuri totale vazute pe kg de branza= cost productie + cost depozitare
// daca costul de productie + cost depozitare per kg < cost de productie pe saptamana curent analizata
//  atunci se merita sa incept sa produc mai mult la acel cost si sa am si depozitat surplusul de branza

// acesta este break point-ul ca index saptamana care imi spune ca este mai rentabil sa produc mai mult decat ce am preconizat
// daca e rentabil atunci pun pe coada dubla indexul de la care incepe optimizarea costului
        while (!index_week.empty() && cost[index_week.back()] + (week - index_week.back()) * s > cost[week])
            index_week.pop_back();

        index_week.push_back(week);
        total_cost = total_cost + (q_sold * (cost[index_week.front()] + (week - index_week.front()) * s));


    }

    fin.close();

    ofstream fout("branza.out");
    fout << total_cost;
    fout.close();

    return 0;

}


























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


// int main()
// {
//     long long n, s, t, cost[100001] = {}, cantitate, cost_total = 0;
//     fin>>n>>s>>t;
//     deque <long long> v;
//     for(int i = 1; i <= n; i++){
//         v.push_back(i);
//         cout << "Runda2"<< " ";
//         // cout<< v[i] << " ";
//         cout<< v.front()<< " ";
//         cout << v.back()<<" ";
//         v.pop_front();
//     }
// }