เร่งดีพีด้วยเปลือกนูน: เมื่อทางเลือกทุกทางเป็นเส้นตรง ก็เหลือแค่เส้นที่ต่ำที่สุด

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* ---- เปลือกล่างแบบเดินทางเดียว ใช้ได้เมื่อความชัน "ลดลง" และคำถาม "เพิ่มขึ้น" ---- */
struct Line { long long m, b; };
static inline long long lineAt(const Line &L, long long x) { return L.m * x + L.b; }

struct Hull {
  vector<Line> st;
  int ptr = 0;
  /* เส้นกลาง b ไม่จำเป็น ถ้าจุดตัดของ a กับเส้นใหม่ c อยู่ซ้ายกว่าหรือตรงกับจุดตัดของ a กับ b
     เขียนเป็นการคูณไขว้ ไม่ใช้ทศนิยม จะได้ไม่มีปัญหาความละเอียด */
  static bool useless(const Line &a, const Line &b, const Line &c) {
    return (__int128)(c.b - a.b) * (a.m - b.m) <= (__int128)(b.b - a.b) * (a.m - c.m);
  }
  void clampPtr() { if (ptr >= (int)st.size()) ptr = (int)st.size() - 1; if (ptr < 0) ptr = 0; }
  void add(Line L) {
    if (!st.empty() && st.back().m == L.m) {          // ชันเท่ากัน เก็บเส้นที่ต่ำกว่า
      if (st.back().b <= L.b) return;
      st.pop_back();
    }
    while (st.size() >= 2 && useless(st[st.size() - 2], st.back(), L)) st.pop_back();
    st.push_back(L);
    clampPtr();
  }
  long long query(long long x) {
    clampPtr();
    while (ptr + 1 < (int)st.size() && lineAt(st[ptr + 1], x) <= lineAt(st[ptr], x)) ptr++;
    return lineAt(st[ptr], x);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n, c;
  if (!(cin >> n >> c)) return 0;
  vector<ll> x(n + 1);
  for (ll i = 1; i <= n; i++) cin >> x[i];

  /* dp[i] = ค่าน้อยสุดที่คลุมจุดที่ 1..i ให้ครบ
     ถ้าหลังคาผืนสุดท้ายคลุมจุด j+1..i ราคาผืนนั้นคือ c + (x[i] - x[j+1])^2
     กระจายกำลังสองออกมา จะได้ dp[j] + x[j+1]^2 - 2*x[j+1]*x[i] + x[i]^2 + c
     ก้อนที่ขึ้นกับ j คือ (-2*x[j+1]) * x[i] + (dp[j] + x[j+1]^2) ซึ่งเป็นเส้นตรงที่ x[i] */
  vector<ll> dp(n + 1, 0);
  Hull h;
  for (ll i = 1; i <= n; i++) {
    ll j = i - 1;                                  // เส้นของ j เพิ่งพร้อมใช้พอดี
    h.add({-2 * x[j + 1], dp[j] + x[j + 1] * x[j + 1]});
    dp[i] = h.query(x[i]) + x[i] * x[i] + c;
  }
  cout << dp[n] << "\n";
  return 0;
}

// เงื่อนไขทิ้งเส้น เวอร์ชันที่ผลคูณล้น
static bool useless(const Line &a, const Line &b, const Line &c) {
  // บรรทัดนี้ผิด: ผลต่างของจุดตัดแกนโตได้ถึงระดับ 2e18 และผลต่างของความชันถึง 4e9
  // คูณกันแล้วเป็น 8e27 ซึ่งล้น long long (เพดานราว 9.2e18) แบบเงียบ ๆ
  return (long long)(c.b - a.b) * (a.m - b.m) <= (long long)(b.b - a.b) * (a.m - c.m);
}

// อินพุตที่เล็กที่สุดเท่าที่ทำให้พัง มีจุดแค่สามจุด
//   3 1000000
//   1
//   999999900
//   1000000000
// เวอร์ชันล้นตอบ 3000000 คือ "คลุมจุดละผืน" สามผืน
// คำตอบจริงคือ 2010000 คือผืนแรกคลุมจุดที่ 1 อย่างเดียวจ่าย 1000000
// ผืนที่สองคลุมสองจุดท้ายซึ่งห่างกัน 100 จ่าย 1000000 + 100*100 = 1010000
//
// เส้นตรงต้องมีสามเส้นขึ้นไปเงื่อนไขนี้จึงถูกเรียกใช้ สามจุดจึงเป็นตัวค้านที่เล็กที่สุดที่มีได้

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* ---- เปลือกล่างแบบเดินทางเดียว ใช้ได้เมื่อความชัน "ลดลง" และคำถาม "เพิ่มขึ้น" ---- */
struct Line { long long m, b; };
static inline long long lineAt(const Line &L, long long x) { return L.m * x + L.b; }

struct Hull {
  vector<Line> st;
  int ptr = 0;
  /* เส้นกลาง b ไม่จำเป็น ถ้าจุดตัดของ a กับเส้นใหม่ c อยู่ซ้ายกว่าหรือตรงกับจุดตัดของ a กับ b
     เขียนเป็นการคูณไขว้ ไม่ใช้ทศนิยม จะได้ไม่มีปัญหาความละเอียด */
  static bool useless(const Line &a, const Line &b, const Line &c) {
    return (__int128)(c.b - a.b) * (a.m - b.m) <= (__int128)(b.b - a.b) * (a.m - c.m);
  }
  void clampPtr() { if (ptr >= (int)st.size()) ptr = (int)st.size() - 1; if (ptr < 0) ptr = 0; }
  void add(Line L) {
    if (!st.empty() && st.back().m == L.m) {          // ชันเท่ากัน เก็บเส้นที่ต่ำกว่า
      if (st.back().b <= L.b) return;
      st.pop_back();
    }
    while (st.size() >= 2 && useless(st[st.size() - 2], st.back(), L)) st.pop_back();
    st.push_back(L);
    clampPtr();
  }
  long long query(long long x) {
    clampPtr();
    while (ptr + 1 < (int)st.size() && lineAt(st[ptr + 1], x) <= lineAt(st[ptr], x)) ptr++;
    return lineAt(st[ptr], x);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  if (!(cin >> n)) return 0;
  vector<ll> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];

  /* dp[i] = ค่าน้อยสุดที่จะโค่นต้นที่ i ให้ล้มสนิท
     ตอนโค่นต้นที่ i ต้นที่ล้มสนิทแล้วซึ่งหมายเลขมากสุดคือ j อยู่ก่อน i
     จึงจ่ายค่าชาร์จ b[j] ต่อหนึ่งฟัน และต้องฟัน a[i] ครั้ง
     dp[i] = min over j<i ของ dp[j] + b[j] * a[i] ซึ่งคือเส้นตรงชัน b[j] ที่ตำแหน่ง a[i] */
  vector<ll> dp(n + 1, 0);
  Hull h;
  h.add({b[1], dp[1]});                            // dp[1] = 0 เพราะ a[1] = 1 และเลื่อยชาร์จมาแล้ว
  for (int i = 2; i <= n; i++) {
    dp[i] = h.query(a[i]);
    h.add({b[i], dp[i]});
  }
  cout << dp[n] << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* ---- เปลือกล่างแบบเดินทางเดียว ใช้ได้เมื่อความชัน "ลดลง" และคำถาม "เพิ่มขึ้น" ---- */
struct Line { long long m, b; };
static inline long long lineAt(const Line &L, long long x) { return L.m * x + L.b; }

struct Hull {
  vector<Line> st;
  int ptr = 0;
  /* เส้นกลาง b ไม่จำเป็น ถ้าจุดตัดของ a กับเส้นใหม่ c อยู่ซ้ายกว่าหรือตรงกับจุดตัดของ a กับ b
     เขียนเป็นการคูณไขว้ ไม่ใช้ทศนิยม จะได้ไม่มีปัญหาความละเอียด */
  static bool useless(const Line &a, const Line &b, const Line &c) {
    return (__int128)(c.b - a.b) * (a.m - b.m) <= (__int128)(b.b - a.b) * (a.m - c.m);
  }
  void clampPtr() { if (ptr >= (int)st.size()) ptr = (int)st.size() - 1; if (ptr < 0) ptr = 0; }
  void add(Line L) {
    if (!st.empty() && st.back().m == L.m) {          // ชันเท่ากัน เก็บเส้นที่ต่ำกว่า
      if (st.back().b <= L.b) return;
      st.pop_back();
    }
    while (st.size() >= 2 && useless(st[st.size() - 2], st.back(), L)) st.pop_back();
    st.push_back(L);
    clampPtr();
  }
  long long query(long long x) {
    clampPtr();
    while (ptr + 1 < (int)st.size() && lineAt(st[ptr + 1], x) <= lineAt(st[ptr], x)) ptr++;
    return lineAt(st[ptr], x);
  }
};

struct Rect { ll x, y, a; };

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  if (!(cin >> n)) return 0;
  vector<Rect> r(n);
  for (auto &t : r) cin >> t.x >> t.y >> t.a;
  sort(r.begin(), r.end(), [](const Rect &p, const Rect &q) { return p.x < q.x; });

  /* โจทย์รับประกันว่าไม่มีรูปไหนซ้อนอยู่ในรูปอื่น เรียงตาม x เพิ่มขึ้นแล้ว y จะลดลงเอง
     f[i] = ค่าดีที่สุดเมื่อรูปที่ i เป็นรูปขวาสุดที่เลือก
     พื้นที่ที่รูปที่ i เพิ่มให้คือ x[i]*y[i] ลบส่วนที่รูปก่อนหน้าคลุมไว้แล้วคือ x[j]*y[i]
     f[i] = x[i]*y[i] - a[i] + max over j<i ของ ( f[j] - x[j]*y[i] )

     ก้อนใน max เป็นเส้นตรงชัน -x[j] ที่ตำแหน่ง y[i] ซึ่งเป็น "ค่ามากสุด" และความชันลดลง
     พลิกเครื่องมือเดิมมาใช้ด้วยการกลับเครื่องหมายทั้งชันและจุดตัด (สะท้อนรูปข้ามแกน x)
     แล้วถามที่ -y[i] ซึ่งเรียงเพิ่มขึ้นพอดี ค่ามากสุดจึงเท่ากับลบของค่าน้อยสุด */
  Hull h;
  h.add({0, 0});                                   // ไม่เลือกรูปไหนก่อนหน้าเลย f = 0
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ll f = r[i].x * r[i].y - r[i].a - h.query(-r[i].y);
    ans = max(ans, f);
    h.add({-r[i].x, -f});
  }
  cout << ans << "\n";
  return 0;
}

/* ตัวตรวจของฝึกข้อ 3: ไล่ทุกสับเซตของรูป แล้วคิดพื้นที่ยูเนียนจากนิยามตรง ๆ
   ไม่ใช้ดีพี ไม่ใช้ข้ออ้างเรื่อง "รูปขวาสุด" และไม่ใช้เรื่องไม่มีรูปซ้อนกันเลย */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct R { ll x, y, a; };

int main() {
  int n;
  if (!(cin >> n)) return 0;
  vector<R> r(n);
  for (auto &t : r) cin >> t.x >> t.y >> t.a;
  ll best = 0;                                     // ไม่เลือกรูปไหนเลยได้ 0
  for (int mask = 1; mask < (1 << n); mask++) {
    vector<R> s;
    for (int i = 0; i < n; i++) if (mask >> i & 1) s.push_back(r[i]);
    vector<ll> xs;
    for (auto &t : s) xs.push_back(t.x);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    ll area = 0, prev = 0;
    for (ll cut : xs) {                            // แถบแนวตั้ง (prev, cut]
      ll top = 0;
      for (auto &t : s) if (t.x >= cut) top = max(top, t.y);
      area += (cut - prev) * top;
      prev = cut;
    }
    ll cost = 0;
    for (auto &t : s) cost += t.a;
    best = max(best, area - cost);
  }
  cout << best << "\n";
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = (ll)4e18;
const int XLO = -100000, XHI = 100000;             // ช่วงของ a[i] ตามขอบเขตโจทย์

/* ---- ต้นไม้ลีเชา เก็บเส้นตรงหนึ่งเส้นต่อหนึ่งปม เดินรากถึงใบแล้วเจอเส้นที่ดีที่สุดแน่ ---- */
struct Node { int lc, rc; ll m, b; };
vector<Node> nd(1, {0, 0, 0, INF});                // ปมที่ 0 คือ "ว่าง" เส้นสูงชนิดไม่มีวันชนะ

static inline ll at(int t, ll x) { return nd[t].m * x + nd[t].b; }

int makeNode(ll m, ll b) {
  nd.push_back({0, 0, m, b});
  return (int)nd.size() - 1;
}

/* ใส่เส้นใหม่ ตัดสินที่จุดกลางว่าเส้นไหนต่ำกว่า เก็บตัวที่ต่ำกว่าไว้ที่ปมนี้
   อีกตัวจะต่ำกว่าได้แค่ครึ่งเดียว จึงส่งลงไปครึ่งนั้น ทำให้ลึกแค่ log ของช่วง

   คืนค่าเป็นหมายเลขปม ไม่รับพารามิเตอร์เป็น int& เพราะ makeNode ทำ push_back
   ซึ่งอาจย้ายตำแหน่งของ vector ทั้งก้อน แล้วอ้างอิงที่ถืออยู่จะชี้ไปที่หน่วยความจำเก่า */
int addLine(int t, int l, int r, ll m, ll b) {
  if (!t) return makeNode(m, b);
  int mid = l + (r - l) / 2;
  bool onLeft = m * l + b < at(t, l);
  bool onMid = m * mid + b < at(t, mid);
  if (onMid) { swap(nd[t].m, m); swap(nd[t].b, b); }
  if (l == r) return t;
  if (onLeft != onMid) {
    int c = addLine(nd[t].lc, l, mid, m, b);
    nd[t].lc = c;
  } else {
    int c = addLine(nd[t].rc, mid + 1, r, m, b);
    nd[t].rc = c;
  }
  return t;
}

/* รวมสองต้นเข้าด้วยกัน รวมลูกก่อน แล้วค่อยยัดเส้นของปมฝั่งที่ถูกกลืนลงไปในต้นที่เหลือ */
int mergeTree(int a, int b, int l, int r) {
  if (!a) return b;
  if (!b) return a;
  int mid = l + (r - l) / 2;
  if (l < r) {
    int cl = mergeTree(nd[a].lc, nd[b].lc, l, mid);
    nd[a].lc = cl;
    int cr = mergeTree(nd[a].rc, nd[b].rc, mid + 1, r);
    nd[a].rc = cr;
  }
  return addLine(a, l, r, nd[b].m, nd[b].b);
}

ll queryTree(int t, int l, int r, ll x) {
  if (!t) return INF;
  ll res = at(t, x);
  if (l == r) return res;
  int mid = l + (r - l) / 2;
  if (x <= mid) return min(res, queryTree(nd[t].lc, l, mid, x));
  return min(res, queryTree(nd[t].rc, mid + 1, r, x));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  if (!(cin >> n)) return 0;
  vector<ll> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  vector<vector<int>> g(n + 1);
  for (int e = 0; e < n - 1; e++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  /* ไล่ต้นไม้ด้วยสแต็กของตัวเอง ไม่ใช้การเรียกซ้ำ เพราะต้นไม้ลึกได้ถึงแสนชั้น */
  vector<int> par(n + 1, 0), order;
  order.reserve(n);
  {
    vector<int> stk{1};
    par[1] = -1;
    while (!stk.empty()) {
      int u = stk.back();
      stk.pop_back();
      order.push_back(u);
      for (int v : g[u]) if (v != par[u]) { par[v] = u; stk.push_back(v); }
    }
  }

  /* dp[u] = ค่าน้อยสุดที่จะกระโดดจาก u ลงไปถึงใบใดก็ได้ในต้นย่อยของ u
     กระโดดครั้งแรกไปที่ v ราคา a[u]*b[v] แล้วจ่ายต่ออีก dp[v]
     ก้อนนี้เป็นเส้นตรงชัน b[v] จุดตัด dp[v] ที่ตำแหน่ง a[u]
     ความชัน b[v] มาแบบไม่เรียง และตำแหน่งถาม a[u] ก็ไม่เรียง จึงใช้ต้นไม้ลีเชา */
  vector<ll> dp(n + 1, 0);
  vector<int> root(n + 1, 0);
  for (int t = (int)order.size() - 1; t >= 0; t--) {
    int u = order[t];
    for (int v : g[u]) if (v != par[u]) root[u] = mergeTree(root[u], root[v], XLO, XHI);
    dp[u] = root[u] ? queryTree(root[u], XLO, XHI, a[u]) : 0;   // ไม่มีลูกคือเป็นใบ จ่าย 0
    root[u] = addLine(root[u], XLO, XHI, b[u], dp[u]);
  }
  for (int i = 1; i <= n; i++) cout << dp[i] << " \n"[i == n];
  return 0;
}

/* ตัวตรวจของฝึกข้อ 4: ไล่ทุกปมในต้นย่อยตรง ๆ ไม่มีต้นไม้ลีเชา ไม่มีเปลือกนูน */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
int n; vector<vector<int>> g; vector<int> par, order_;
int main(){
  if(!(cin>>n))return 0;
  vector<ll>a(n+1),b(n+1);
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++)cin>>b[i];
  g.assign(n+1,{});
  for(int e=0;e<n-1;e++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
  par.assign(n+1,0);
  vector<int>stk{1};par[1]=-1;
  while(!stk.empty()){int u=stk.back();stk.pop_back();order_.push_back(u);
    for(int v:g[u])if(v!=par[u]){par[v]=u;stk.push_back(v);}}
  // ปมในต้นย่อยของแต่ละ u
  vector<vector<int>>sub(n+1);
  for(int t=(int)order_.size()-1;t>=0;t--){int u=order_[t];sub[u].push_back(u);
    for(int v:g[u])if(v!=par[u])for(int w:sub[v])sub[u].push_back(w);}
  vector<ll>dp(n+1,0);
  for(int t=(int)order_.size()-1;t>=0;t--){int u=order_[t];ll best=INF;
    for(int v:sub[u])if(v!=u)best=min(best,a[u]*b[v]+dp[v]);
    dp[u]=(best==INF?0:best);}
  for(int i=1;i<=n;i++)cout<<dp[i]<<" \n"[i==n];
}

// ต้นไม้ลีเชา เวอร์ชันแรกที่ผมเขียน ซึ่งผิด
// ปมเก็บใน vector<Node> nd แล้วรับพารามิเตอร์เป็นอ้างอิงไปยังช่องลูก
void addLine(int &t, int l, int r, ll m, ll b) {
  // makeNode ข้างล่างทำ nd.push_back() ซึ่งถ้า vector เต็มจะจองบล็อกใหม่แล้วย้ายข้อมูลทั้งก้อน
  // ตอนนั้น t ที่เป็นอ้างอิงไปยัง nd[...].lc ของบล็อกเก่า กลายเป็นอ้างอิงค้าง
  if (!t) { t = makeNode(m, b); return; }

  int mid = l + (r - l) / 2;
  bool onLeft = m * l + b < at(t, l);
  bool onMid = m * mid + b < at(t, mid);
  if (onMid) { swap(nd[t].m, m); swap(nd[t].b, b); }
  if (l == r) return;

  // สองบรรทัดนี้คือจุดตาย ส่ง nd[t].lc เข้าไปเป็นอ้างอิง
  // แล้วข้างในนั้นมีการ push_back ซึ่งย้าย nd ทั้งก้อน
  // การเขียนค่ากลับจึงไปลงที่หน่วยความจำที่ถูกปล่อยแล้ว เส้นที่ใส่หายไปเงียบ ๆ
  if (onLeft != onMid) addLine(nd[t].lc, l, mid, m, b);
  else addLine(nd[t].rc, mid + 1, r, m, b);
}

// อาการ: ตัวอย่างที่หนึ่งของโจทย์ผ่าน (10 50 0) แต่ตัวอย่างที่สองตอบ
//   -50 100 0 0
// ขณะที่คำตอบคือ
//   -300 100 0 0
// ปมที่ 1 ควรกระโดดไปปมที่ 2 ด้วยราคา 5 * (-80) = -400 แล้วต่อไปปมที่ 4 อีก 100 รวม -300
// แต่เส้นของปมที่ 2 หายไปจากต้นไม้ที่ถูกรวมขึ้นมา จึงเหลือทางที่แย่กว่าคือกระโดดตรงไปปมที่ 4 ได้ -50
//
// ทางแก้: ให้ addLine คืนหมายเลขปมกลับมา แล้วเขียนค่าลง nd[t].lc หลังการเรียกจบ
// ตอนนั้น nd ถูกมองใหม่แล้ว จึงไม่มีอ้างอิงค้างข้ามการ push_back อีก