1 /************************************************************** 2     Problem: 3437 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:1616 ms 7     Memory:32056 kb 8 ****************************************************************/ 9  10 #include <cstdio>11  12 #define L q[l]13 using namespace std;14 typedef long long ll;15 const int N = 1000005;16  17 int n, l, r;18 ll f[N], g[N], q[N];19 ll sum1[N], sum2;20  21 inline int read() {22     int x = 0;23     char ch = getchar();24     while (ch < ‘0‘ || ‘9‘ < ch)25         ch = getchar();26     while (‘0‘ <= ch && ch <= ‘9‘) {27         x = x * 10 + ch - ‘0‘;28         ch = getchar();29     }30     return x;31 }32  33 inline ll calc1(int x, int y) {34     return (ll) g[x] - g[y];35 }36  37 inline ll calc2(int x, int y) {38     return (ll) sum1[x] - sum1[y];39 }40  41 inline bool pop_head(int x, int i) {42     return calc1(q[x + 1], q[x]) < i * calc2(q[x + 1], q[x]);43 }44  45 inline bool pop_tail(int x, int i) {46     return calc1(i, q[x]) * calc2(q[x], q[x - 1]) < calc1(q[x], q[x - 1]) * calc2(i, q[x]);47 }48  49 int main() {50     int i, b;51     n = read();52     for (i = 1; i <= n; ++i)53         f[i] = read();54     for (l = r = 0, i = 1; i <= n; ++i) {55         b = read();56         sum1[i] = sum1[i - 1] + b;57         sum2 += (ll) i * b;58  59         while (l < r && pop_head(l, i)) ++l;60         f[i] += g[L] + i * (sum1[i] - sum1[L]) - sum2;61         g[i] = f[i] + sum2;62         while (l < r && pop_tail(r, i)) --r;63         q[++r] = i;64     }65     printf("%lld\n", f[n]);66     return 0;67 }