#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int N = 3e6;
const int MAX = 1e16;
struct Line{
int k, b;
Line(int k = MAX, int b = MAX) : k(k), b(b) {}
};
int F(Line &a, int x){
if(a.k == MAX && a.b == MAX) return -MAX;
return -(a.k*x + a.b);
}
struct LiChao{
struct Node{
Line k;
Node *l, *r;
Node(){
l = nullptr, r = nullptr;
}
};
int n;
Node *root;
LiChao(int sz) : n(sz), root(nullptr) {}
void addLine(Node *&p, int l, int r, Line &a){
if(!p) p = new Node();
int mid = (l + r) / 2;
int l_side = F(a, l) > F(p->k, l);
int m_side = F(a, mid) > F(p->k, mid);
if(m_side) p->k = a;
if(l == r-1) return;
if(l_side == m_side){
addLine(p->r, mid, r, a);
}else{
addLine(p->l, l, mid, a);
}
}
void addLine(Line a){
addLine(root, -n, n, a);
}
int get(Node *&p, int l, int r, int x){
if(!p) return -MAX;
if(l == r-1){
return F(p->k, x);
}
int mid = (l + r) / 2;
if(mid > x){
return max(F(p->k, x), get(p->l, l, mid, x));
}else{
return max(F(p->k, x), get(p->r, mid, r, x));
}
}
int get(int x){
return get(root, -n, n, x);
}
};
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
signed main(){
int n; cin >> n;
vector<int> h(n+1);
for(int i = 1;i <= n; i++) cin >> h[i];
vector<int> w(n+1, 0);
for(int i = 1;i <= n; i++){
cin >> w[i];
w[i]+= w[i-1];
}
LiChao lch((int)1e9);
vector<int> dp(n+1, MAX);
dp[1] = 0;
lch.addLine(Line(h[1], dp[1] - w[1] + h[1] * h[1]));
for(int i = 2;i <= n; i++){
// kx + b
/*
new_dp[i] = (h[i] - h[j])^2 + dp[j]
(h[i] - h[j]) * (h[i] - h[j]) = kx
h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j]
dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
*/
/*int ans = MAX;
for(int j = 1; j < i; j++){
ans = min(ans, -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
//dp[i] = min(dp[i], -2 * h[i] * h[j] + dp[j] - w[j] + h[j] * h[j] + w[i-1] + h[i] * h[i]);
}
*/
int mn = lch.get(-2*h[i]);
mn = -mn;
//cout << i << " = " << ans << " , " << mn + h[i] * h[i] + w[i-1] << '\n';
dp[i] = min(dp[i], mn + h[i]*h[i] + w[i-1]);
lch.addLine(Line(h[i], dp[i] - w[i] + h[i] * h[i]));
}
cout << dp[n];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
3780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
