Pagini recente » Cod sursa (job #1550052) | Cod sursa (job #2793969) | Diferente pentru home intre reviziile 374 si 373 | Istoria paginii runda/listare-onis | Cod sursa (job #2007573)
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
deque <int> dq;
int n, S, T;
long long d[MAXN], cf[MAXN];
int main()
{
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
int i, P, C;
scanf("%d%d%d", &n, &S, &T);
for(i=1; i<=n; ++i) {
scanf("%d%d", &C, &P);
d[i] = 1LL * C * P;
while(!dq.empty() && i - dq.front() > T)
dq.pop_front();
if(!dq.empty())
d[i] = min(d[i], 1LL * P * i * S + P * cf[dq.front()]);
d[i] += d[i-1];
cf[i] = C - S * i;
while(!dq.empty() && cf[i] < cf[dq.back()])
dq.pop_back();
dq.push_back(i);
}
printf("%lld", d[n]);
return 0;
}