#include #include #include #define llint long long #define inf 1e18 using namespace std; typedef pair P; struct LiChaoTree{ int size; vector

seg; LiChaoTree(){} LiChaoTree(int size){ this->size = size; seg.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(0, inf); } llint calc(P f, llint x) { return f.first * x + f.second; } llint query(int x) //xにおける最小値を取得 { int i = x + (1 << size); llint ret = inf; while(i >= 1){ ret = min(ret, calc(seg[i], x)); i /= 2; } return ret; } void add(int k, int l, int r, P f) { int m = (l+r)/2; if(calc(f, m) < calc(seg[k], m)) swap(seg[k], f); bool L = (calc(f, l) < calc(seg[k], l)), R = (calc(f, r) < calc(seg[k], r)); if(L == R) return; if(L) add(k*2, l, m, f); if(R) add(k*2+1, m+1, r, f); } void addSegment(int a, int b, int k, int l, int r, P f) { if(b < l || r < a) return; if(a <= l && r <= b){ add(k, l, r, f); return; } addSegment(a, b, k*2, l, (l+r)/2, f); addSegment(a, b, k*2+1, (l+r)/2+1, r, f); } void addSegment(int a, int b, llint p, llint q) //区間[a, b]に線分px+qを追加 { addSegment(a, b, 1, 0, (1<> n; for(int i = n; i >= 1; i--) cin >> a[i]; for(int i = n; i >= 1; i--) cin >> x[i]; for(int i = n; i >= 1; i--) cin >> y[i]; lct.init(); dp[0] = 0; lct.addSegment(a[1], (1<<17)-1, 1, -a[1]+dp[0]); lct.addSegment(0, a[1]-1, -1, a[1]+dp[0]); for(int i = 1; i <= n; i++){ dp[i] = lct.query(x[i]) + y[i]; lct.addSegment(a[i+1], (1<<17)-1, 1, -a[i+1]+dp[i]); lct.addSegment(0, a[i+1]-1, -1, a[i+1]+dp[i]); } cout << dp[n] << endl; return 0; }