Cod sursa(job #2889398)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 12 aprilie 2022 18:43:23
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <deque>
using namespace std;

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

deque <pair<long long, long long>> bestOffer;               ///pret si index zi
long long nrZile, pretDepozit, zileMaxDepozit, pretAzi, cerereAzi, sum, i, costDepozitBestOffer;


int main()
{
    fin >> nrZile >> pretDepozit >> zileMaxDepozit;
    fin >> pretAzi >> cerereAzi;
    sum += pretAzi * cerereAzi;
    bestOffer.push_back(make_pair(pretAzi, 0));
    for (i = 1; i < nrZile; i++)
    {
        costDepozitBestOffer += pretDepozit;
        fin >> pretAzi >> cerereAzi;
        if (i - zileMaxDepozit > bestOffer.front().second)
        {
            bestOffer.pop_front();
            costDepozitBestOffer = (i-bestOffer.front().second)*pretDepozit;
        }

        if (bestOffer.front().first + costDepozitBestOffer < pretAzi)
        {
            while (pretAzi < bestOffer.back().first + (i-bestOffer.back().second)*pretDepozit)
                bestOffer.pop_back();
            bestOffer.push_back(make_pair(pretAzi, i));
            sum += (bestOffer.front().first + costDepozitBestOffer) * cerereAzi;
        }
        else
        {
            while (pretAzi <= bestOffer.front().first + costDepozitBestOffer)
            {
                bestOffer.pop_front();
                costDepozitBestOffer-=pretDepozit;
                if (bestOffer.size() == 0)
                {
                    costDepozitBestOffer = 0;
                    break;
                }

            }
            sum += pretAzi * cerereAzi;
            bestOffer.push_back(make_pair(pretAzi, i));
        }
    }
    fout << sum;
    return 0;
}