#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];
class ConvexHullTrick {
struct line {
long long m, b, value;
double xlo;
bool is_query, query_max;
line(long long m, long long b, long long v, bool is_query, bool query_max)
: m(m), b(b), value(v), xlo(-std::numeric_limits<double>::max()),
is_query(is_query), query_max(query_max) {}
double intersect(const line &l) const {
if (m == l.m) return std::numeric_limits<double>::max();
return (double)(l.b - b)/(m - l.m);
}
bool operator<(const line &l) const {
if (l.is_query) return query_max ? (xlo < l.value) : (l.value < xlo);
return m < l.m;
}
};
std::set<line> hull;
bool query_max;
typedef std::set<line>::iterator hulliter;
bool has_prev(hulliter it) const {
return it != hull.begin();
}
bool has_next(hulliter it) const {
return (it != hull.end()) && (++it != hull.end());
}
bool irrelevant(hulliter it) const {
if (!has_prev(it) || !has_next(it)) return false;
hulliter prev = it, next = it;
--prev;
++next;
return query_max ? (prev->intersect(*next) <= prev->intersect(*it))
: (next->intersect(*prev) <= next->intersect(*it));
}
hulliter update_left_border(hulliter it) {
if ((query_max && !has_prev(it)) || (!query_max && !has_next(it))) return it;
hulliter it2 = it;
double value = it->intersect(query_max ? *--it2 : *++it2);
line l(*it);
l.xlo = value;
hull.erase(it++);
return hull.insert(it, l);
}
public:
ConvexHullTrick(bool query_max = false) : query_max(query_max) {}
void add(long long m, long long b) {
line l(m, b, 0, false, query_max);
hulliter it = hull.lower_bound(l);
if (it != hull.end() && it->m == l.m) {
if ((query_max && it->b < b) || (!query_max && b < it->b)) hull.erase(it++);
else return;
}
it = hull.insert(it, l);
if (irrelevant(it)) {
hull.erase(it);
return;
}
while (has_prev(it) && irrelevant(--it)) hull.erase(it++);
while (has_next(it) && irrelevant(++it)) hull.erase(it--);
it = update_left_border(it);
if (has_prev(it)) update_left_border(--it);
if (has_next(++it)) update_left_border(++it);
}
long long query(long long x) const {
line q(0, 0, x, true, query_max);
hulliter it = hull.lower_bound(q);
if (query_max) --it;
return it->m*x + it->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:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
building.cpp:99: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:100: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 |
2 ms |
1144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
2936 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 |
2 ms |
1144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
