#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define el '\n'
const int N = 1e6 + 24;
const ll INF = 4e18;
int n; ll h[N], w[N];
ll pre[N], dp[N];
struct Line {
ll a, b;
ll calc(ll x) { return a * x + b; }
};
struct Lichao {
int n; vector<Line> t;
Lichao(int sz) : t(4 * sz + 24, {0, LLONG_MAX}), n(sz) {}
void update(int id, int l, int r, Line f) {
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.calc(l) < t[id].calc(l)) update(2 * id, l, mid, f);
else update(2 * id + 1, mid + 1, r, f);
}
ll get(int id, int l, int r, int i) {
int mid = (l + r) >> 1;
ll cur = t[id].calc(i);
if (i == mid) return cur;
else if (i < mid) return min(get(2 * id, l, mid, i), cur);
else return min(get(2 * id + 1, mid + 1, r, i), cur);
}
};
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + w[i];
}
Lichao lct(N);
dp[1] = 0;
for (int i = 1; i <= n; i++) {
if (i > 1) dp[i] = h[i] * h[i] + pre[i - 1] + lct.get(1, 0, N, h[i]);
lct.update(1, 0, N, {-2 * h[i], dp[i] + h[i] * h[i] - pre[i]});
}
cout << dp[n] << el;
}
int main() {
cin.tie(NULL) -> sync_with_stdio(false);
#define task "file"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int T = 1; // cin >> T;
while (T--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
building.cpp: In function 'int main()':
building.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |