#include <bits/stdc++.h>
using namespace std;
inline namespace
{
template <typename T>
T fl_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template <typename T>
struct Line
{
T m, c;
T operator()(T x) const { return m * x + c; }
};
template <typename T>
struct LineContainerObject
{
T m, c;
mutable T p;
bool operator<(const LineContainerObject &i_line) const { return m < i_line.m; }
bool operator<(T x) const { return p < x; }
};
template <typename T>
struct LineContainer : multiset<LineContainerObject<T>, less<>>
{
void add(const Line<T> &line)
{
auto it = this->insert({line.m, line.c, 0});
while (isect(it))
this->erase(next(it));
if (it != this->begin() && isect(--it))
{
this->erase(next(it));
isect(it);
}
while (it != this->begin() && isect(--it))
{
this->erase(next(it));
isect(it);
}
}
T query(T x)
{
auto it = this->lower_bound(x);
return it->m * x + it->c;
}
private:
inline static const T INF = numeric_limits<T>::max();
bool isect(typename multiset<LineContainerObject<T>, less<>>::iterator it)
{
if (next(it) == this->end())
{
it->p = INF;
return 0;
}
if (it->m == next(it)->m)
it->p = it->c > next(it)->c ? INF : -INF;
else
it->p = fl_div(next(it)->c - it->c, it->m - next(it)->m);
return it->p >= next(it)->p;
}
};
} // namespace
void solve()
{
int n;
cin >> n;
vector<long> h(n), w(n);
for (long &x : h)
cin >> x;
for (long &x : w)
cin >> x;
long add = 0;
for (long x : w)
add += x;
vector<long> dp(n);
LineContainer<long> cht;
dp[0] = w[0];
cht.add(Line<long>{2 * h[0], dp[0] - h[0] * h[0]});
for (int i = 1; i < n; i++)
{
dp[i] = cht.query(h[i]) - h[i] * h[i] + w[i];
cht.add(Line<long>{2 * h[i], dp[i] - h[i] * h[i]});
}
cout << -dp[n - 1] + add << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
2644 KB |
Output is correct |
2 |
Correct |
43 ms |
2884 KB |
Output is correct |
3 |
Correct |
42 ms |
2732 KB |
Output is correct |
4 |
Correct |
41 ms |
2672 KB |
Output is correct |
5 |
Correct |
43 ms |
3764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
42 ms |
2644 KB |
Output is correct |
7 |
Correct |
43 ms |
2884 KB |
Output is correct |
8 |
Correct |
42 ms |
2732 KB |
Output is correct |
9 |
Correct |
41 ms |
2672 KB |
Output is correct |
10 |
Correct |
43 ms |
3764 KB |
Output is correct |
11 |
Correct |
49 ms |
2672 KB |
Output is correct |
12 |
Correct |
42 ms |
2644 KB |
Output is correct |
13 |
Correct |
34 ms |
2672 KB |
Output is correct |
14 |
Correct |
42 ms |
2724 KB |
Output is correct |
15 |
Correct |
54 ms |
8908 KB |
Output is correct |
16 |
Correct |
43 ms |
3788 KB |
Output is correct |
17 |
Correct |
28 ms |
2644 KB |
Output is correct |
18 |
Correct |
21 ms |
2668 KB |
Output is correct |