Pagini recente » Cod sursa (job #1964114) | Cod sursa (job #2740628) | Cod sursa (job #2233212) | Cod sursa (job #2525210) | Cod sursa (job #2889398)
#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;
}