#include<iostream>
#include<cstring>
#define MAXN 100001
using namespace std;
long long n, total, h[MAXN], w[MAXN], cur, dp[MAXN];
struct Line
{
long long m, b;
Line() {}
Line(long long _m, long long _b)
{
m = _m;
b = _b;
}
long long operator() (long long x)
{
return m * x + b;
}
};
struct LiChao
{
Line arr[40 * MAXN];
void add(int ind, int l, int r, Line seg)
{
if(l == r)
{
if(arr[ind](l) < seg(l))
{
arr[ind] = seg;
}
return;
}
int mid = (l + r) / 2;
if(seg.m > arr[ind].m) swap(arr[ind], seg);
if(arr[ind](mid) > seg(mid))
{
swap(arr[ind], seg);
add(ind * 2 + 1, l, mid, seg);
}
else
{
add(ind * 2 + 2, mid + 1, r, seg);
}
}
long long query(int ind, int l, int r, int x)
{
if(l == r)
{
return arr[ind](x);
}
int mid = (l + r) / 2;
long long ans = arr[ind](x);
if(x <= mid) return min(ans, query(ind * 2 + 1, l, mid, x));
else return min(ans, query(ind * 2 + 2, mid + 1, r, x));
}
}tree;
void read()
{
cin>>n;
for(int i = 0; i < n; i ++)
{
cin>>h[i];
}
for(int i = 0; i < n; i ++)
{
cin>>w[i];
total += w[i];
}
}
void solve()
{
cur = 0;
tree.add(0, 0, 1e6 + 1, Line(-2 * h[0], h[0] * h[0] + cur));
for(int i = 1; i < n; i ++)
{
cur = tree.query(0, 0, 1e6 + 1, h[i]) - w[i] + h[i] * h[i];
//cout<<cur<<": "<<tree.query(0, 0, 1e6 + 1, h[i])<<" "<<-w[i]<<" "<<h[i]<<endl;
tree.add(0, 0, 1e6 + 1, Line(-2 * h[i], cur + h[i] * h[i]));
}
cout<<cur + total<<endl;
}
int main()
{
read();
solve();
return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
3716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
