Submission #1112003

#TimeUsernameProblemLanguageResultExecution timeMemory
1112003AvianshBuilding Bridges (CEOI17_building)C++17
30 / 100
3070 ms3408 KiB
#include <bits/stdc++.h> using namespace std; long long inf = 2e18; signed main(){ ios::sync_with_stdio(0); cin.tie(0); long long n; cin >> n; long long arr[n]; for(long long &i : arr){ cin >> i; } long long w[n]; for(long long &i : w){ cin >> i; } long long dp[n]; dp[0]=0; dp[1]=arr[0]*arr[0]+arr[1]*arr[1]-2*arr[0]*arr[1]; long long pref[n]; pref[0]=w[0]; for(int i = 1;i<n;i++){ pref[i]=pref[i-1]+w[i]; } for(long long i = 2;i<n;i++){ long long sm = 0; dp[i]=inf; for(long long j = i-1;j>=0;j--){ dp[i]=min(dp[i],dp[j]+pref[i-1]-pref[j]+arr[i]*arr[i]+arr[j]*arr[j]-2*arr[i]*arr[j]); sm+=w[j]; } } cout << dp[n-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...