#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i) #define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i) #define all(x) x.begin(), x.end() #define uni(x) x.erase(unique(all(x)), x.end()) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define dbg(...) cerr << "[ " << #__VA_ARGS__ << " ] = ", debug(__VA_ARGS__) template<typename T> void debug(T x) { cerr << x << "\n\n"; } template<typename T, typename... Args> void debug(T x, Args... args) { cerr << x << " , ", debug(args...); } // -------------------------------------------------------------------------------------------------------------------- const int maxn = 1e5 + 3; int n; ll h[maxn], w[maxn], preW[maxn], dp[maxn]; // -------------------------------------------------------------------------------------------------------------------- struct Line { ll a, b; Line() {a = 0, b = 1e18;} Line(ll a, ll b) : a(a), b(b) {} ll eval(ll x) {return a * x + b;} }; namespace LCT { Line seg[1000001]; void addLine(int l, int r, Line f) { if (l > r) return; int mid = l + r >> 1; if (seg[mid].eval(mid) > f.eval(mid)) swap(seg[mid], f); if (l == r) return; if (f.a < seg[mid].a) addLine(mid + 1, r, f); else if (f.a > seg[mid].a) addLine(l, mid - 1, f); } ll getMin(int l, int r, ll pos) { int mid = l + r >> 1; ll res = seg[mid].eval(pos); if (pos < mid) res = min(res, getMin(l, mid - 1, pos)); else if (pos > mid) res = min(res, getMin(mid + 1, r, pos)); return res; } } void solve() { cin >> n; FOR(i, 1, n) cin >> h[i]; FOR(i, 1, n) { cin >> w[i]; preW[i] = preW[i - 1] + w[i]; } int maxVal = *max_element(h + 1, h + n + 1); dp[1] = 0; FOR(i, 2, n) { LCT :: addLine(0, maxVal, Line(-2 * h[i - 1], dp[i - 1] + h[i - 1] * h[i - 1] - preW[i - 1])); dp[i] = LCT :: getMin(0, maxVal, h[i]) + h[i] * h[i] + preW[i - 1]; } cout << dp[n]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TASK "TEST" if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } solve(); return 0; }

building.cpp: In function 'int main()':
building.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~