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>
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define inf 1000000000000000
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
ll Wsum = 0;
vi h(n);
rep(i,n){
cin >> h[i];
}
vi w(n);
rep(i,n){
cin >> w[i];
Wsum += w[i];
}
vi dp(n, inf);
dp[0] = -w[0];
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
dp[i] = min(dp[i], dp[j] + (h[i] - h[j])*(h[i] - h[j]) - w[i]);
}
}
cout << dp[n-1] + Wsum << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |