Pagini recente » Cod sursa (job #1796493) | Cod sursa (job #2411311) | Cod sursa (job #3186099) | Cod sursa (job #821604) | Cod sursa (job #459990)
Cod sursa(job #459990)
#include <cstdio>
#define nmax 100005
#define ll long long
#define inf 10000000
using namespace std;
ll dp[nmax], sol;
int cant[nmax], cost[nmax], i, j;
int N, S, T, front, back;
int D[nmax];
int main () {
freopen ("branza.in", "r", stdin);
freopen ("branza.out", "w", stdout);
scanf ("%d%d%d\n", &N, &S, &T);
for (i = 1; i <= N; i++) scanf ("%d%d\n", &cost[i], &cant[i]);
dp[1] = cost[1];
front = 1; back = 0;
for (i = 1; i <= N; i++) {
dp[i] = cost[i];
while (front <= back && dp[i] <= dp[ D[back] ] + (i - D[back]) * S) --back;
D[++back] = i;
dp[i] = dp[ D[front] ] + (i - D[front]) * S;
if (D[front] == i - T) ++front;
}
for (i = 1; i <= N; i++) {
sol += cant[i] * dp[i];
}
printf ("%lld\n", sol);
return 0;
}