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