Pagini recente » Cod sursa (job #600809) | Cod sursa (job #2388483) | Cod sursa (job #3212494) | Cod sursa (job #3287516) | Cod sursa (job #3270481)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 1e5 + 1;
int N, S, T;
long long C[N_MAX];
void SetInput(string name)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
(void)!freopen((name + ".in").c_str(), "r", stdin);
(void)!freopen((name + ".out").c_str(), "w", stdout);
}
void Solve()
{
int sol = 0;
deque<int> dq; /// OBS: dq este ordonat descrecator, iar dq.front() reprez cea mai mica suma curenta de platit per branza
cin >> N >> S >> T;
int P;
for(int i = 0, j; i < N; i++)
{
cin >> C[i] >> P;
if(dq.front() == i - T - 1)
dq.pop_front();
while(not dq.empty())
{
j = dq.back();
if(C[j] + S * (i - j) > C[i])
dq.pop_back();
else
break;
}
dq.push_back(i);
j = dq.front();
sol += P * (C[j] + S * (i - j));
}
cout << sol;
}
int main()
{
SetInput("branza");
Solve();
return 0;
}