Pagini recente » Cod sursa (job #2714873) | Cod sursa (job #2259760) | Cod sursa (job #3000229) | Cod sursa (job #915751) | Cod sursa (job #2887716)
#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;
}