#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vf first
#define vs second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
struct Line {
ll m = 0 , c = 1e18;
};
ll value(Line a , int x){
return a.m * x + a.c;
}
struct Lichao {
vector<Line> v;
int siz;
void init(int n){
siz = 1;
while(siz < n){
siz *= 2;
}
v.resize(siz * 2);
}
void set(Line l, int x , int lx , int rx){
if(rx - lx == 0){
if(value(l,lx) < value(v[x],lx)){
v[x] = l;
}
return;
}
int m = (lx + rx)/2;
if(v[x].m < l.m)swap(v[x],l);
if(value(l,m) < value(v[x] , m)){
swap(l,v[x]);
set(l , 2 * x , lx , m);
}
else {
set(l , 2 * x + 1 , m + 1 ,rx);
}
}
ll query(int x_val , int x , int lx, int rx){
ll ans = value(v[x],x_val);
if(rx == lx)return ans;
int mid = (lx + rx)/2;
if(x_val <= mid){
ans = min(ans , query(x_val , 2 *x, lx,mid));
}
else ans = min(ans , query(x_val, 2 * x + 1 , mid + 1 ,rx));
return ans;
}
};
void solve(){
int n;
cin >> n;
ll h[n];
for(int i = 0; i < n; i++){
cin >> h[i];
}
ll w[n];
for(int i = 0; i < n; i++){
cin >> w[i];
}
ll dp[n];
Lichao li;
li.init(1000005);
dp[0] = -w[0];
li.set({-2*h[0] , h[0]*h[0] + w[0]},0,0,li.siz-1);
ll ans = 0;
for(int i = 0; i < n; i++){
ans += w[i];
}
for(int i = 1; i < n; i++){
dp[i] = li.query(h[i],0,0,li.siz-1) + h[i] * h[i] - w[i];
li.set({-2*h[i] , h[i]*h[i] +dp[i]},0,0,li.siz-1);
}
cout << dp[n-1] + ans << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;
//cin >> t;
// while(t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
36444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
33112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
