Submission #1126476

#TimeUsernameProblemLanguageResultExecution timeMemory
1126476vladiliusBuilding Bridges (CEOI17_building)C++20
30 / 100
3091 ms2628 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second const ll inf = numeric_limits<ll> :: max(); int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; vector<int> h(n + 1), w(n + 1); for (int i = 1; i <= n; i++){ cin>>h[i]; } vector<ll> p(n + 1); for (int i = 1; i <= n; i++){ cin>>w[i]; p[i] = p[i - 1] + w[i]; } auto sum = [&](int l, int r){ return p[r] - p[l - 1]; }; auto sq = [&](int x){ return 1LL * x * x; }; vector<ll> dp(n + 1); for (int i = 2; i <= n; i++){ dp[i] = inf; for (int j = 1; j < i; j++){ dp[i] = min(dp[i], dp[j] + sum(j + 1, i - 1) + sq(h[i] - h[j])); } } cout<<dp[n]<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...