Submission #468942

#TimeUsernameProblemLanguageResultExecution timeMemory
468942AutumnBuilding Bridges (CEOI17_building)C++17
30 / 100
89 ms131076 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...