#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define debug(x) cerr << #x << " = " << x << endl
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1 << (i))
#define FULL(i) (MASK(i) - 1)
#define __builtin_popcount __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T, class T2>
ostream &operator<<(ostream &o, pair<T, T2> p)
{
o << "(" << p.first << ", " << p.second << ")";
return o;
}
const int M = 1e5 + 5;
ll f[M], h[M], w[M], pre[M];
template<
typename T, // for segment & coordinates data types, e.g. long long
typename TM // for intermediate computations, e.g. __int128_t
> struct LiChao {
LiChao(const vector<T>& _xs) : xs(_xs) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
n = xs.size();
head = 1;
while (head < n) head <<= 1;
lines.assign(head * 2, {0, 0, -1, false});
xyz.resize(head * 2);
for (int i = 0; i < n; i++) {
xyz[head + i] = {xs[i], xs[i], xs[i]};
}
for (int i = head - 1; i; i--) {
int l = i*2, r = i*2 + 1;
xyz[i] = {
std::get<0>(xyz[l]),
std::get<0>(xyz[r]),
std::get<2>(xyz[r]),
};
}
}
void add_line(T a, T b, int idx = -1) {
ql = 0, qr = n;
if (ql >= qr) return;
rec(1, 0, head, Line{a, b, idx, true});
}
void add_segment(T left, T right, T a, T b, int idx = -1) {
ql = std::lower_bound(xs.begin(), xs.end(), left) - xs.begin();
qr = std::lower_bound(xs.begin(), xs.end(), right) - xs.begin();
if (ql >= qr) return;
rec(1, 0, head, Line{a, b, idx, true});
}
struct Result {
T line_a, line_b;
int line_id;
bool is_valid; // if false -> result is INFINITY
TM minval;
};
Result get(T x) {
int i = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();
assert(i < n && xs[i] == x);
return get(i, x);
}
// private:
int n, head;
vector<T> xs; // coordinates of all get queries
struct Line {
T a, b; // a*x + b
int id;
bool is_valid;
TM f(T x) const { return TM(a) * x + b; }
};
vector<Line> lines;
vector<tuple<T, T, T>> xyz; // <left, mid, right>
int ql, qr;
void rec(int i, int l, int r, Line new_line) {
const int mid = (l + r) / 2;
if (l >= qr || r <= ql) {
return;
} else if (ql <= l && r <= qr) {
if (!lines[i].is_valid) {
lines[i] = new_line;
return;
}
auto [x, y, z] = xyz[i];
bool upd_x = lines[i].f(x) > new_line.f(x);
bool upd_y = lines[i].f(y) > new_line.f(y);
bool upd_z = lines[i].f(z) > new_line.f(z);
if (upd_x && upd_y && upd_z) {
lines[i] = new_line;
return;
}
if (upd_y && upd_z) {
std::swap(lines[i], new_line);
rec(i*2, l, mid, new_line);
} else if (upd_x && upd_y) {
std::swap(lines[i], new_line);
rec(i*2 + 1, mid, r, new_line);
} else if (upd_x) {
rec(i*2, l, mid, new_line);
} else if (upd_z) {
rec(i*2+1, mid, r, new_line);
} else {
return;
}
} else {
if (ql < mid) rec(i*2, l, mid, new_line);
if (qr > mid) rec(i*2+1, mid, r, new_line);
}
}
Result get(int i, T x) {
i += head;
Line res = lines[i];
TM val = res.is_valid ? res.f(x) : 0;
for (i /= 2; i; i /= 2) {
if (!lines[i].is_valid) continue;
TM tmp = lines[i].f(x);
if (!res.is_valid || tmp < val) res = lines[i], val = tmp;
}
return {res.a, res.b, res.id, res.is_valid, val};
}
};
ll sqr(ll x)
{
return x * x;
}
signed main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> h[i];
for (int i = 1; i <= n; ++i)
cin >> w[i];
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + w[i];
vector <ll> xCods;
for (int i = 1; i <= n; ++i)
xCods.push_back(h[i]);
LiChao<ll, ll> st(xCods);
for (int i = 2; i <= n; ++i)
{
int p = i - 1;
st.add_line(-2 * h[p], sqr(h[p]) + f[p] - pre[p]);
for (int j = 1; j < i; ++j)
f[i] = sqr(h[i]) + pre[i - 1] + st.get(h[i]).minval;
}
cout << f[n];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3014 ms |
6152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2648 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2652 KB |
Output is correct |
| 6 |
Execution timed out |
3014 ms |
6152 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
