Pagini recente » Cod sursa (job #1320187) | Cod sursa (job #2596880) | Cod sursa (job #2265075) | Cod sursa (job #2080679) | Cod sursa (job #3281492)
#include <bits/stdc++.h>
std::ifstream fin("branza.in");
std::ofstream fout("branza.out");
const int size = 1e5 + 5;
int n, s, t;
int cost[size], demand[size];
std::deque<int> deque;
void read();
void solve();
int main()
{
read();
solve();
return 0;
}
void read()
{
fin >> n >> s >> t;
for(int i = 1; i <= n; ++i)
fin >> cost[i] >> demand[i];
}
void solve()
{
int64_t ans = 0;
for(int i = 1; i <= n; ++i)
{
// cat timp ne costa mai mult
while(!deque.empty() && (cost[deque.back()] + s * (i - deque.back())) >= cost[i])
deque.pop_back();
// am gasit un index optim care poate fi folosit mai departe
deque.push_back(i);
// branza este expirata
if(deque.front() < i - t)
deque.pop_front();
// adaug la costul total pretul minim pt ziua i
ans += (int64_t) demand[i] * (cost[deque.front()] + s * (i - deque.front()));
}
fout << ans;
}