Pagini recente » Cod sursa (job #258033) | Cod sursa (job #1546442) | Cod sursa (job #165541) | Cod sursa (job #1224299) | Cod sursa (job #1804406)
#include <cstdio>
#include <iostream>
#include <deque>
using namespace std;
const int nmx = 100002;
int n,s,t;
long long c[nmx],p[nmx];
long long dp[nmx];
deque <pair<int,int> > dq;
void citire()
{
scanf("%d %d %d", &n, &s, &t);
for(int i = 1; i <= n; ++i)
scanf("%lld %lld", &c[i], &p[i]);
}
void dinamica()
{
for(int i = 1; i <= n; ++i)
{
while(not dq.empty() && dq.back().second + (i-dq.back().first) * s > c[i])
dq.pop_back();
dq.push_back(make_pair(i,c[i]));
while(not dq.empty() && dq.front().first < i - t)
dq.pop_front();
dp[i] = dp[i-1] + min(c[i]*p[i],p[i]*dq.front().second+(i-dq.front().first)*s*p[i]);
}
}
void afish()
{
printf("%lld\n", dp[n]);
}
int main()
{
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
citire();
dinamica();
afish();
return 0;
}