#include <bits/stdc++.h>
#define maxn 100001
#define maxx 100000
#define inf 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll, ll> line;
int n, M, h[N], w[N], a[N];
ll dp[N];
ll f(line l, int x) {
if (l.first == inf && l.second == inf)
return ll(inf) * inf;
return l.first * a[x] + l.second;
}
line L[4 * maxn];
void add_line(line nw, int v = 1, int l = 1, int r = M) {
if (f(nw, l) >= f(L[v], l) && f(nw, r) >= f(L[v], r))
return;
if (f(nw, l) <= f(L[v], l) && f(nw, r) <= f(L[v], r)) {
swap(L[v], nw);
return;
}
int m = (l + r) / 2;
bool lef = f(nw, l) < f(L[v], l);
bool mid = f(nw, m) < f(L[v], m);
if(mid)
swap(L[v], nw);
if(r - l == 1)
return;
else
if(lef != mid) {
add_line(nw, 2 * v, l, m);
} else {
add_line(nw, 2 * v + 1, m, r);
}
}
ll get(int x, int v = 1, int l = 1, int r = M) {
int m = (l + r) / 2;
if(r - l == 1)
return f(L[v], x);
else
if(x < m)
return min(f(L[v], x), get(x, 2 * v, l, m));
else
return min(f(L[v], x), get(x, 2 * v + 1, m, r));
}
#define task "BUILD"
int main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> h[i];
for(int i = 1; i <= n; ++i)
cin >> w[i];
set<int> tmp;
for(int i = 1; i <= n; ++i)
tmp.insert(h[i]);
M = 0;
for(int x : tmp)
a[++M] = x;
for(int i = 1; i <= n; ++i)
h[i] = lower_bound(a + 1, a + M + 1, h[i]) - a;
for(int i = 1; i <= 4 * M; ++i)
L[i] = make_pair(inf, inf);
dp[1] = -w[1];
add_line(make_pair(-2 * a[h[1]], dp[1] + ll(a[h[1]])*a[h[1]]));
for(int i = 2; i <= n; ++i) {
dp[i] = ll(a[h[i]]) * a[h[i]] - w[i] + get(h[i]);
add_line(make_pair(-2 * a[h[i]], dp[i] + ll(a[h[i]])*a[h[i]]));
}
ll ans = dp[n];
for(int i = 1; i <= n; ++i)
ans += w[i];
cout << ans;
}
Compilation message
building.cpp:9:13: error: 'N' was not declared in this scope
9 | int n, M, h[N], w[N], a[N];
| ^
building.cpp:9:19: error: 'N' was not declared in this scope
9 | int n, M, h[N], w[N], a[N];
| ^
building.cpp:9:25: error: 'N' was not declared in this scope
9 | int n, M, h[N], w[N], a[N];
| ^
building.cpp:10:7: error: 'N' was not declared in this scope
10 | ll dp[N];
| ^
building.cpp: In function 'll f(line, int)':
building.cpp:14:22: error: 'a' was not declared in this scope
14 | return l.first * a[x] + l.second;
| ^
building.cpp: In function 'int main()':
building.cpp:62:16: error: 'h' was not declared in this scope
62 | cin >> h[i];
| ^
building.cpp:64:16: error: 'w' was not declared in this scope
64 | cin >> w[i];
| ^
building.cpp:68:20: error: 'h' was not declared in this scope
68 | tmp.insert(h[i]);
| ^
building.cpp:71:9: error: 'a' was not declared in this scope
71 | a[++M] = x;
| ^
building.cpp:73:9: error: 'h' was not declared in this scope
73 | h[i] = lower_bound(a + 1, a + M + 1, h[i]) - a;
| ^
building.cpp:73:28: error: 'a' was not declared in this scope
73 | h[i] = lower_bound(a + 1, a + M + 1, h[i]) - a;
| ^
building.cpp:77:5: error: 'dp' was not declared in this scope
77 | dp[1] = -w[1];
| ^~
building.cpp:77:14: error: 'w' was not declared in this scope
77 | dp[1] = -w[1];
| ^
building.cpp:78:29: error: 'a' was not declared in this scope
78 | add_line(make_pair(-2 * a[h[1]], dp[1] + ll(a[h[1]])*a[h[1]]));
| ^
building.cpp:78:31: error: 'h' was not declared in this scope
78 | add_line(make_pair(-2 * a[h[1]], dp[1] + ll(a[h[1]])*a[h[1]]));
| ^
building.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
