Pagini recente » Cod sursa (job #3158699) | Cod sursa (job #2524999) | Cod sursa (job #2701505) | Cod sursa (job #748280) | Cod sursa (job #3226173)
#include <fstream>
#include <deque>
#define int long long
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
const int NMAX = 1e5 + 5, inf = 1e9;
int ans, N, S, T, C[NMAX], P[NMAX], dp[NMAX];
deque<int> dq;
signed main()
{
cin >> N >> S >> T;
for(int i = 1; i <= N; i++)
cin >> C[i] >> P[i], dp[i] = inf;
for(int i = 1; i <= N; i++)
{
if(dq.empty())
dp[i] = C[i], dq.push_back(i);
else
{
while(dq.front() < i - T)
dq.pop_front();
while(!dq.empty() && C[dq.back()] + (i - dq.back()) * S >= C[i])
dq.pop_back();
dq.push_back(i);
dp[i] = C[dq.front()] + (i - dq.front()) * S;
}
}
for(int i = 1; i <= N; i++)
ans = ans + dp[i] * P[i];
cout << ans;
}