This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
vector<int> h;
vector<int> w;
vector<vector<int>> memo;
vector<vector<bool>> been;
int dp(int i, int last){
if(been[i][last])return memo[i][last];
been[i][last]=true;
if(i==(int)h.size()-1)return memo[i][last]=(h[i]-h[last])*(h[i]-h[last]);
int a=dp(i+1, i)+ (h[i]-h[last])*(h[i]-h[last]);
int b=dp(i+1,last)+w[i];
return memo[i][last]=min(a,b);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
h.resize(n);
w.resize(n);
for(int i=0;i<n;i++){
cin>>h[i];
}
for(int i=0;i<n;i++){
cin>>w[i];
}
memo.resize(n,vector<int> (n));
been.resize(n,vector<bool> (n));
int costs=dp(1,0);
cout<<costs<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |