#include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define int long long const int N=3e5+5; int h[N],w[N]; int dp[N]; struct Line { long long m, b; // y = m*x + b long long eval(long long x) const { return m*x + b; } }; struct LiChao { struct Node { Line ln; Node *l, *r; Node(Line v): ln(v), l(nullptr), r(nullptr) {} }; Node* root = nullptr; long long L, R; // domain of x LiChao(long long left, long long right): L(left), R(right) {} Node* add(Node* node, long long l, long long r, Line nw) { if(!node) return new Node(nw); long long mid = (l + r) >> 1; // At mid, keep the better line if( node->ln.eval(mid) > nw.eval(mid) ) swap(node->ln, nw); if(l == r) return node; if( nw.eval(l) < node->ln.eval(l) ) node->l = add(node->l, l, mid, nw); else if( nw.eval(r) < node->ln.eval(r) ) node->r = add(node->r, mid+1, r, nw); return node; } void add_line(long long m, long long b) { Line ln = {m, b}; root = add(root, L, R, ln); } long long query(Node* node, long long l, long long r, long long x) const { if(!node) return LLONG_MAX / 4; long long res = node->ln.eval(x); if(l == r) return res; long long mid = (l + r) >> 1; if(x <= mid) return min(res, query(node->l, l, mid, x)); else return min(res, query(node->r, mid+1, r, x)); } long long query(long long x) const { return query(root, L, R, x); } }; signed main(){ int n; cin>>n; int k=0; for(int i=1;i<=n;i++){ cin>>h[i]; } for(int i=1;i<=n;i++){ cin>>w[i]; k+=w[i]; } dp[1]=h[1]*h[1]-h[n]*h[n]; for(int i=2;i<=n;i++){ dp[i]=1e18; } LiChao cht(0, 1e6); cht.add_line(-2*h[1], dp[1]); for(int i = 2; i <= n; i++){ long long p = h[i]*h[i]*2 - w[i]; long long best = cht.query(h[i]); dp[i] = best + p; cht.add_line(-2*h[i], dp[i]); } cout<<dp[n]+k-w[1]; } /*6 3 8 7 1 6 6 0 -1 9 1 2 0 */

building.c:1:9: fatal error: bits/stdc++.h: No such file or directory
    1 | #include<bits/stdc++.h>
      |         ^~~~~~~~~~~~~~~
compilation terminated.