#include<bits/stdc++.h>
using namespace std;
using ld = long double;
#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;
void setIO(string name){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(!name.empty()){
freopen((name + ".in").c_str(),"r",stdin);
freopen((name + ".out").c_str(),"w",stdout);
}
}
int val[maxN],h[maxN],w[maxN];
struct Line{
int m = INF,c = INF;
int operator()(int x){
return m*val[x] + c;
}
};
Line st[4*maxN];
void insert(int pos, int l, int r, Line L){
if(l == r){
if(L(l) < st[pos](l)) st[pos] = L;
return;
}
int mid = (l+r)/2;
if(st[pos].m < L.m) swap(st[pos],L);
if(st[pos](mid) > L(mid)){
swap(st[pos],L);
insert(2*pos,l,mid,L);
return;
}
insert(2*pos+1,mid+1,r,L);
}
int query(int pos, int l, int r, int x){
if(l == r){
return st[pos](x);
}
int mid = (l+r)/2;
if(x > mid) return min(st[pos](x),query(2*pos+1,mid+1,r,x));
return min(st[pos](x),query(2*pos,l,mid,x));
}
int dp[maxN];
signed main(){
setIO("");
int n; cin >> n;
vi nums;
int tot = 0;
forn(i,n){
cin >> h[i];
nums.pb(h[i]);
}
sort(all(nums));
forn(i,n){
val[i] = nums[i];
}
forn(i,n){
cin >> w[i];
tot += w[i];
}
dp[0] = -w[0];
Line C = {-2*h[0],h[0]*h[0]+dp[0]};
insert(1,0,n-1,C);
forrange(i,1,n){
int idx = lower_bound(all(nums),h[i]) - nums.begin();
dp[i] = query(1,0,n-1,idx) + h[i]*h[i] - w[i];
Line D = {-2*h[i],h[i]*h[i]+dp[i]};
insert(1,0,n-1,D);
}
cout << tot + dp[n-1] << endl;
}
/*
dp[i] = the min. cost of making a bridge from 1 to i with removing the unnecessary pillars
dp[i] = min(dp[j] + (h[i]-h[j])^2 - w[i])
dp[i] = min(-2*h[j]*h[i] + h[j]^2 + dp[j]) + h[i]^2 - w[i]
*/
Compilation message
building.cpp: In function 'void setIO(std::string)':
building.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen((name + ".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((name + ".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
61 ms |
11732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |