Pagini recente » Cod sursa (job #17024) | Cod sursa (job #1133982) | Cod sursa (job #2934585) | Cod sursa (job #1610198) | Cod sursa (job #2852147)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
deque <int> q;
int n, depozit, sapt;
int cost[100001], cantitate[100001];
void citire()
{
fin >> n >> depozit >> sapt;
for(int i = 0; i < n; ++i)
{
fin >> cost[i] >> cantitate[i];
}
}
int pret(int i, int j)
{
int p = (cost[j] + (i - j) * depozit);
return p;
}
void adaugare(int i)
{
while(!q.empty() && pret(i, q.back()) >= cost[i])
q.pop_back();
while(!q.empty() && (i - q.front()) > sapt)
q.pop_front();
q.push_back(i);
}
long long suma()
{
long long s = 0;
for(int i = 0; i < n; ++i)
{
adaugare(i);
//cout << q.front() << ' ' << i << '\n';
s += (cost[q.front()] + (i - q.front()) * depozit) * cantitate[i];
}
return s;
}
int main()
{
citire();
fout << suma();
return 0;
}