Pagini recente » Cod sursa (job #2405804) | Cod sursa (job #2954537) | Cod sursa (job #742216) | Cod sursa (job #1983810) | Cod sursa (job #2500079)
#include <cstdio>
#include <deque>
using namespace std;
const long long MAX_N = 100000;
struct Index {
long long val;
long long index;
};
long long n, s, t;
long long c[1 + MAX_N];
long long p[1 + MAX_N];
deque<Index> dq;
long long back_cost(long long i) {
//fprintf(stderr, "%d %d\n", dq.back().val, dq.back().index);
return 1LL * p[i + 1] * (dq.back().val + (i + 1 - dq.back().index) * s);
}
int main() {
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
scanf("%lld%lld%lld", &n, &s, &t);
for (long long i = 1; i <= n; i++) {
scanf("%lld%lld", &c[i], &p[i]);
}
long long ans;
ans = 1LL * p[1] * c[1];
dq.push_back({c[1], 1});
for (long long i = 2; i <= n; i++) {
ans += min(1LL * p[i] * c[i], 1LL * p[i] * (dq.front().val + (i - dq.front().index) * s));
if (i < n) {
long long iCost = 1LL * p[i + 1] * (c[i] + s);
while (dq.size() > 0 && iCost <= back_cost(i))
dq.pop_back();
dq.push_back({c[i], i});
while (i - dq.front().index > t)
dq.pop_front();
}
}
printf("%lld\n", ans);
return 0;
}