李超树优化dp板子
#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;
const int N = 500010;
struct Line {
Line() {}
Line(i64 k, i64 b) : k(k), b(b) {}
i64 k, b;
i64 f(i64 x) {
return k * x + b;
}
} line[N];
int root, idx;
int T[N * 20], ls[N * 20], rs[N * 20];
i64 f[N], t[N], F[N];
int n;
Line get(int i) {
return Line(t[i], f[i] / 2 - F[i]);
}
int maxline(int a, int b, int x) {
if (!a || !b) return a | b;
return line[a].f(x) > line[b].f(x) ? a : b;
}
void insert(int& u, int l, int r, int id) {
if (!u) u = ++idx;
int& t = T[u];
if (!t) return t = id, void();
int mid = l + r >> 1;
if (line[id].f(mid) > line[t].f(mid)) swap(id, t);
if (line[id].f(l) > line[t].f(l)) insert(ls[u], l, mid, id);
if (line[id].f(r) > line[t].f(r)) insert(rs[u], mid + 1, r, id);
}
int query(int u, int l, int r, int x) {
if (!u || l == r) return T[u];
int mid = l + r >> 1, res = T[u];
if (x <= mid) res = maxline(res, query(ls[u], l, mid, x), x);
else res = maxline(res, query(rs[u], mid + 1, r, x), x);
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
for (int i = 1; i <= n; i++) {
cin >> F[i];
}
line[1] = get(1);
insert(root, 1, 20000, 1);
i64 res = 0;
for (int i = 2; i <= n; i++) {
int id = query(1, 1, 20000, t[i]);
f[i] = line[id].f(t[i]);
res = max(res, f[i]);
line[i] = get(i);
insert(root, 1, 20000, i);
}
cout << res << '\n';
return 0;
}