include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define INF 1e18
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
#define TASK "test"
using namespace std;
const int N = 100005;
const int mod = 1e9 + 7;
int n, h[N], w[N];
struct Line{
ll a, b;
Line(ll a = 0, ll b = INF): a(a), b(b) {}
ll calc(int x){
return a * x + b;
}
ll sl(){
return a;
}
};
namespace lichao{
vector<Line> t;
void init(){
t.resize(4000001, Line());
}
void ins(Line f, int id = 1, int l = 1, int r = 1e6){
if (l == r){
if (f.calc(l) < t[id].calc(l)){
t[id] = f;
}
return;
}
int mid = (l + r) >> 1;
if (f.calc(mid) < t[id].calc(mid)) swap(f, t[id]);
if (f.sl() > t[id].sl()){
ins(f, id << 1, l, mid);
}
else ins(f, id << 1 | 1, mid + 1, r);
}
ll get(ll x, int id = 1, int l = 1, int r = 1e6){
int mid = (l + r) >> 1;
ll cur = t[id].calc(x);
if (l == r) return cur;
if (x <= mid) return min(cur, get(x, id << 1, l, mid));
return min(cur, get(x, id << 1 | 1, mid + 1, r));
}
};
void Proc(){
cin >> n;
FOR(i, 1, n) cin >> h[i];
FOR(i, 1, n) {
cin >> w[i];
w[i] += w[i - 1];
}
//dp[i] = dp[j] + (h[i] - h[j])^2 + pre[i - 1] - pre[j]
//dp[i] = - 2*h[j]*h[i] + dp[j] + h[j]*h[j] - pre[j] + h[i]*h[i] + pre[i - 1];
lichao::init();
lichao::ins(Line(-2 * h[1], h[1] * h[1] - w[1]));
FOR(i, 2, n){
ll val = lichao::get(h[i]) + h[i] * h[i] + w[i - 1];
lichao::ins(Line(-2 * h[i], val + h[i] * h[i] - w[i]));
}
cout << lichao::get(h[n]) + h[n] * h[n] + w[n - 1];
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; T = 1;
//cin >> T;
while (T--) Proc();
}
Compilation message (stderr)
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:10: error: 'bits' was not declared in this scope
1 | include <bits/stdc++.h>
| ^~~~
building.cpp:1:15: error: 'stdc' was not declared in this scope; did you mean 'std'?
1 | include <bits/stdc++.h>
| ^~~~
| std
building.cpp:1:1: error: 'include' does not name a type
1 | include <bits/stdc++.h>
| ^~~~~~~
building.cpp:34:5: error: 'vector' does not name a type
34 | vector<Line> t;
| ^~~~~~
building.cpp: In function 'void lichao::init()':
building.cpp:36:9: error: 't' was not declared in this scope
36 | t.resize(4000001, Line());
| ^
building.cpp: In function 'void lichao::ins(Line, long long int, long long int, long long int)':
building.cpp:40:29: error: 't' was not declared in this scope
40 | if (f.calc(l) < t[id].calc(l)){
| ^
building.cpp:46:27: error: 't' was not declared in this scope
46 | if (f.calc(mid) < t[id].calc(mid)) swap(f, t[id]);
| ^
building.cpp:46:44: error: 'swap' was not declared in this scope
46 | if (f.calc(mid) < t[id].calc(mid)) swap(f, t[id]);
| ^~~~
building.cpp:47:22: error: 't' was not declared in this scope
47 | if (f.sl() > t[id].sl()){
| ^
building.cpp: In function 'long long int lichao::get(long long int, long long int, long long int, long long int)':
building.cpp:55:18: error: 't' was not declared in this scope
55 | ll cur = t[id].calc(x);
| ^
building.cpp:57:30: error: 'min' was not declared in this scope; did you mean 'mid'?
57 | if (x <= mid) return min(cur, get(x, id << 1, l, mid));
| ^~~
| mid
building.cpp:58:16: error: 'min' was not declared in this scope; did you mean 'mid'?
58 | return min(cur, get(x, id << 1 | 1, mid + 1, r));
| ^~~
| mid
building.cpp: In function 'void Proc()':
building.cpp:64:5: error: 'cin' was not declared in this scope
64 | cin >> n;
| ^~~
building.cpp:78:5: error: 'cout' was not declared in this scope
78 | cout << lichao::get(h[n]) + h[n] * h[n] + w[n - 1];
| ^~~~
building.cpp: At global scope:
building.cpp:81:1: error: 'int32_t' does not name a type
81 | int32_t main() {
| ^~~~~~~
building.cpp:1:1: note: 'int32_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
+++ |+#include <cstdint>
1 | include <bits/stdc++.h>