Pagini recente » Cod sursa (job #2917673) | Cod sursa (job #853084) | Cod sursa (job #2240373) | Cod sursa (job #3268225) | Cod sursa (job #3270487)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 1e5 + 1;
int N, T;
long long S;
struct branza
{
int index;
long long cost;
};
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()
{
long long sol = 0;
deque<branza> dq; /// OBS: dq este ordonat descrecator, iar dq.front() reprez cea mai mica suma curenta de platit per branza
cin >> N >> S >> T;
long long P, C;
branza temp;
for(int i = 0; i < N; i++)
{
cin >> C >> P;
if(dq.front().index == i - T - 1)
dq.pop_front();
while(not dq.empty())
{
temp = dq.back();
if(S * (i - temp.index) + temp.cost > C)
dq.pop_back();
else
break;
}
dq.push_back(branza{i, C});
temp = dq.front();
sol += P * (S * (i - temp.index) + temp.cost);
}
cout << sol;
}
int main()
{
SetInput("branza");
Solve();
return 0;
}