Cod sursa(job #2887716)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 10 aprilie 2022 02:36:50
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <queue>
using namespace std;

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

queue <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(make_pair(pretAzi, 0));
    for (i = 1; i < nrZile; i++)
    {
        costDepozitBestOffer += pretDepozit;
        fin >> pretAzi >> cerereAzi;
        if (i - bestOffer.front().second +1> zileMaxDepozit)
        {
            bestOffer.pop();
            costDepozitBestOffer = (i-bestOffer.front().second)*pretDepozit;
        }

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

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