#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000006LL;
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer {
multiset<Line, less<>> sett;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b);
}
bool isect(multiset<Line, less<>>::iterator x, multiset<Line, less<>>::iterator y) {
if (y == sett.end()) {
x->p = INF;
return false;
}
if (x->k == y->k) {
if (x->m > y->m) {
x->p = -INF;
} else x->p = INF;
} else {
x->p = div(x->m - y->m, y->k - x->k);
}
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = sett.insert({k, m, 0});
auto y = z;
auto x = y;
z++;
while (isect(y, z)) z = sett.erase(z);
if (x != sett.begin() && isect(--x, y)) isect(x, y = sett.erase(y));
while ((y = x) != sett.begin() && (--x)->p >= y->p ) {
isect(x, sett.erase(y));
}
}
ll query(ll x) {
assert(!sett.empty());
auto l = *sett.lower_bound(x);
return l.k * x + l.m;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<ll> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
vector<ll> w(n);
for (int i = 0; i < n; i++) cin >> w[i];
ll sum = 0;
for (int i = 0; i < n; i++) sum += w[i];
LineContainer lc;
vector<ll> dp(n);
dp[0] = -w[0];
for (int i = 0; i < n; i++) {
dp[i] -= w[i];
if (i != 0) {
dp[i] -= lc.query(h[i]);
dp[i] += h[i] * h[i];
}
lc.add(2 * h[i], -h[i] * h[i] - dp[i]);
}
cout << (dp[n - 1] + sum) << "\n";
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
3696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
