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

seg; vector x; LiChaoTree(){} LiChaoTree(int size){ this->size = size; seg.resize(1<<(size+1)); x.resize(1<= 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, x[m]) < calc(seg[k], x[m])) swap(seg[k], f); bool L = (calc(f, x[l]) < calc(seg[k], x[l])), R = (calc(f, x[r]) < calc(seg[k], x[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) //区間[x[a], x[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; }