1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 3000000 + 5;
const int Q_MIN = 0;
const int Q_MAX = 1;
const int Q_PRE = 0;
const int Q_SUF = 1;
const LL INF = 3 * LL(1E12) + 5;
int n;
int a[MAX_N], b[MAX_N];
int lNext[MAX_N], rNext[MAX_N];
LL pre[MAX_N], suf[MAX_N];
LL preMin[MAX_N << 2], preMax[MAX_N << 2], sufMin[MAX_N << 2], sufMax[MAX_N << 2];
inline int ls(int o) {
return o << 1;
}
inline int rs(int o) {
return o << 1 | 1;
}
inline void pushUp(int o) {
preMin[o] = min(preMin[ls(o)], preMin[rs(o)]);
preMax[o] = max(preMax[ls(o)], preMax[rs(o)]);
sufMin[o] = min(sufMin[ls(o)], sufMin[rs(o)]);
sufMax[o] = max(sufMax[ls(o)], sufMax[rs(o)]);
}
void build(int o, int l, int r) {
if (l == r) {
preMin[o] = preMax[o] = pre[l];
sufMin[o] = sufMax[o] = suf[l];
return;
}
int mid = (l + r) >> 1;
build(ls(o), l, mid);
build(rs(o), mid + 1, r);
pushUp(o);
}
LL query(int qType, int qArr, int o, int l, int r, int L, int R) {
if (L <= l && r <= R) {
if (qType == Q_MIN && qArr == Q_PRE) return preMin[o];
if (qType == Q_MAX && qArr == Q_PRE) return preMax[o];
if (qType == Q_MIN && qArr == Q_SUF) return sufMin[o];
if (qType == Q_MAX && qArr == Q_SUF) return sufMax[o];
}
int mid = (l + r) >> 1;
LL ret = (qType == Q_MIN ? INF : -INF);
if (L <= mid) {
if (qType == Q_MIN) ret = min(ret, query(qType, qArr, ls(o), l, mid, L, R));
if (qType == Q_MAX) ret = max(ret, query(qType, qArr, ls(o), l, mid, L, R));
}
if (R > mid) {
if (qType == Q_MIN) ret = min(ret, query(qType, qArr, rs(o), mid + 1, r, L, R));
if (qType == Q_MAX) ret = max(ret, query(qType, qArr, rs(o), mid + 1, r, L, R));
}
return ret;
}
void getNext() {
for (int i = 1; i <= n; ++i) lNext[i] = rNext[i] = i;
a[0] = a[n + 1] = -(int(1E6) + 5);
for (LL i = 1; i <= n; ++i) {
while(a[i] <= a[lNext[i] - 1]) lNext[i] = lNext[lNext[i] - 1];
}
for (LL i = n; i >= 1; --i) {
while(a[i] <= a[rNext[i] + 1]) rNext[i] = rNext[rNext[i] + 1];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1; i <= n; ++i) scanf("%d", b + i);
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + b[i];
for (int i = n; i >= 1; --i) suf[i] = suf[i + 1] + b[i];
build(1, 1, n);
getNext();
LL ans = -INF;
for (int i = 1; i <= n; ++i) {
if (a[i] > 0) {
LL lCon = 0, rCon = 0;
if (lNext[i] <= i) lCon = query(Q_MAX, Q_SUF, 1, 1, n, lNext[i], i) - suf[i + 1];
if (i + 1 <= rNext[i]) rCon = query(Q_MAX, Q_PRE, 1, 1, n, i + 1, rNext[i]) - pre[i];
ans = max(ans, a[i] * (lCon + rCon));
} else if (a[i] == 0) {
ans = max(ans, 0LL);
} else {
LL lCon = 0, rCon = 0;
if (lNext[i] <= i) lCon = query(Q_MIN, Q_SUF, 1, 1, n, lNext[i], i) - suf[i + 1];
if (i + 1 <= rNext[i]) rCon = query(Q_MIN, Q_PRE, 1, 1, n, i + 1, rNext[i]) - pre[i];
ans = max(ans, a[i] * (lCon + rCon));
}
}
printf("%lld\n", ans);
return 0;
}
|