#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const long long inf = 1LL << 62;
int n, h[N], w[N];
long long dp[N], f[N];
int state (int a, int b) {
return a > b ? 1 : (a < b ? -1 : 0);
}
struct ConvexHullTrick {
struct Line {
long long a, b; // y = ax + b
mutable function <const Line*()> succ;
Line (long long a, long long b): a(a), b(b) {};
bool operator < (const Line &rhs) const {
if (rhs.b != inf) return a < rhs.a;
const Line* s = succ();
if (!s) return false;
int x = rhs.a;
return b - s -> b < (s -> a - a) * x;
}
};
multiset <Line> s;
bool bad (multiset <Line> ::iterator x) {
auto z = next(x);
if (x == s.begin()) {
if (z == s.end()) return false;
return x -> a == z -> a && x -> b <= z -> b;
}
auto y = prev(x);
if (z == s.end()) return x -> a == y -> a && x -> b <= y -> b;
int l1 = state(y -> b, x -> b), l2 = state(z -> a, x -> a), r1 = state(x -> b, z -> b), r2 = state(x -> a, y -> a);
int lef = l1 * l2, rig = r1 * r2;
if (lef == 0 && rig == 0) return true;
if (lef != rig) return lef > rig;
long double val1 = (long double)(y -> b - x -> b) / (x -> b - z -> b);
long double val2 = (long double)(x -> a - y -> a) / (z -> a - x -> a);
if (lef == 1 && rig == 1) return val1 >= val2;
return val1 <= val2;
}
void add (long long a, long long b) {
auto x = s.insert(Line(a, b));
x -> succ = [=] {
return next(x) == s.end() ? 0 : &*next(x);
};
if (bad(x)) {
s.erase(x);
return;
}
while (next(x) != s.end() && bad(next(x))) s.erase(next(x));
while (x != s.begin() && bad(prev(x))) s.erase(prev(x));
}
long long query (long long x) {
if (s.size() == 0) return 0;
auto found = *s.lower_bound(Line(x, inf));
return found.a * x + found.b;
}
} slope;
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= n; i++) f[i] = f[i - 1] + w[i];
//dp(i) = max(dp(j) + f(i - 1) - f(j) + hi^2 + hj^2 - 2hihj | j < i)
//dp(i) = max(-2hjhi + hj^2 + dp(j) - f(j) + f(i - 1) + hi^2 | j < i)
memset(dp, 0x3f, sizeof(dp));
dp[1] = 0;
slope.add(-2 * h[1], 1LL * h[1] * h[1] + dp[1] - f[1]);
for (int i = 2; i <= n; i++) {
dp[i] = slope.query(h[i]) + f[i - 1] + 1LL * h[i] * h[i];
slope.add(-2 * h[i], 1LL * h[i] * h[i] + dp[i] - f[i]);
}
printf("%lld", dp[n]);
return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
Compilation message
building.cpp: In function 'int main()':
building.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
building.cpp:75:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
~~~~~^~~~~~~~~~~~~
building.cpp:76:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
