#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;
ll n;
vi h;
vi w;
int main(){
cin.sync_with_stdio(false);
cin>>n;
h.resize(n);
w.resize(n);
rep(i,0,n)
cin>>h[i];
ll sumW = 0;
rep(i,0,n){
cin>>w[i];
sumW += w[i];
}
if(n<=1000){
vi dp(n,1e18);
dp[0] = -w[0];
rep(i,1,n){
rep(j,0,i){
dp[i] = min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j]));
}
dp[i] -= w[i];
//cout<<dp[i]<<" ";
}
cout<<sumW + dp[n-1]<<endl;
} else {
ll best = 1e18;
rep(i,1,n-1){
best = min(best,(h[0]-h[i])*(h[0]-h[i]) + (h[n-1]-h[i])*(h[n-1]-h[i]) - w[i]);
}
vector<set<ll> > toLeft(41);
rep(i,1,n-1){
ll target = (h[i]+h[0])/2;
rep(j,0,41){
auto it = toLeft[j].lower_bound(target);
if(it!=toLeft[j].end()){
best = min(best,(h[0]-*it)*(h[0]-*it) + (h[i]-*it)*(h[i]-*it) - (j-20) - w[i]);
}
if(it!=toLeft[j].begin()){
it--;
best = min(best,(h[0]-*it)*(h[0]-*it) + (h[i]-*it)*(h[i]-*it) - (j-20) - w[i]);
}
}
toLeft[w[i]+20].insert(h[i]);
}
best += sumW - w[0] - w[n-1];
cout<<best<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
432 KB |
Output is correct |
4 |
Correct |
3 ms |
508 KB |
Output is correct |
5 |
Correct |
3 ms |
508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
556 ms |
4900 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
432 KB |
Output is correct |
4 |
Correct |
3 ms |
508 KB |
Output is correct |
5 |
Correct |
3 ms |
508 KB |
Output is correct |
6 |
Incorrect |
556 ms |
4900 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |