Pagini recente » Cod sursa (job #2340734) | Cod sursa (job #2032707) | Cod sursa (job #618188) | Cod sursa (job #95289) | Cod sursa (job #549214)
Cod sursa(job #549214)
#include <cstdio>
using namespace std;
const int N = 100005;
long long P[N], C[N], d[N], n, S, T;
int main() {
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
long long i, front = 1, back = 0;
long long rez = 0, min;
scanf("%lld %lld %lld", &n, &S, &T);
for(i = 1; i <= n; ++i)
scanf("%lld %lld", &C[i], &P[i]);
for(i = 1; i <= n; ++i) {
min = P[i] * C[i];
if(front <= back && (C[d[front]] - S * d[front] + S * i) * P[i] < min)
min = (C[d[front]] - S * d[front] + S * i) * P[i];
if(d[back] - d[front] + 1 == T)
++front;
while(front <= back && C[i] - S * i <= C[d[front]] - S * d[front])
--back;
d[++back] = i;
rez += min;
}
printf("%lld\n", rez);
return 0;
}