#include <bits/stdc++.h>
using namespace std;
#define taskname "mvu"
#define ll long long
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
#define all(v) v.begin(), v.end()
struct line {
ll a, b;
line() : a(0), b() {}
line (ll a, ll b) : a(a), b(b) {}
ll calc (ll x) { return a * x + b; }
ll slope() { return a; }
};
struct liChao {
vector<line> tr;
liChao() {}
liChao (int sz) : tr(sz + 1, line(0, LLONG_MAX)) {}
void update (line f, int l, int r) {
if (l > r) return;
int mid = (l + r) >> 1;
if (l == r) {
tr[mid] = (f.calc(l) < tr[mid].calc(l) ? f : tr[mid]);
return;
}
if (f.slope() < tr[mid].slope()) swap(tr[mid], f);
if (tr[mid].calc(mid) < f.calc(mid)) {
update(f, l, mid - 1);
}
else {
update(tr[mid], mid + 1, r);
tr[mid] = f;
}
}
ll query (int p, int l, int r) {
int mid = (l + r) >> 1;
ll cur = tr[mid].calc(p);
if (p == mid) return cur;
if (p < mid) return min(query(p, l, mid - 1), cur);
if (p > mid) return min(query(p, mid + 1, r), cur);
}
};
const int M = 1e6 + 1;
ll dp[M], h[M], w[M];
ll f1 (int k) {
return -2 * h[k];
}
ll f2 (int k) {
return dp[k] + h[k] * h[k] - w[k];
}
ll f3 (int k) {
return h[k] * h[k] + w[k - 1];
}
int main()
{
if(fopen(taskname".inp","r"))
{
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> h[i];
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[i] += w[i - 1];
}
liChao tree(M);
tree.update(line(f1(1), f2(1)), 0, M);
for (int i = 2; i <= n; i++) {
dp[i] = tree.query(h[i], 0, M) + f3(i);
tree.update(line(f1(i), f2(i)), 0, M);
}
cout << dp[n];
return 0;
}
Compilation message
building.cpp:4:12: error: 'long long long' is too long for GCC
4 | #define ll long long
| ^~~~
building.cpp:8:19: note: in expansion of macro 'll'
8 | typedef long long ll;
| ^~
building.cpp:4:17: error: 'long long long' is too long for GCC
4 | #define ll long long
| ^~~~
building.cpp:8:19: note: in expansion of macro 'll'
8 | typedef long long ll;
| ^~
building.cpp:4:17: error: declaration does not declare anything [-fpermissive]
4 | #define ll long long
| ^~~~
building.cpp:8:19: note: in expansion of macro 'll'
8 | typedef long long ll;
| ^~
building.cpp: In function 'int main()':
building.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp: In member function 'long long int liChao::query(int, int, int)':
building.cpp:52:5: warning: control reaches end of non-void function [-Wreturn-type]
52 | }
| ^
