Submission #585583

#TimeUsernameProblemLanguageResultExecution timeMemory
585583tengiz05Building Bridges (CEOI17_building)C++17
30 / 100
3048 ms3412 KiB
#include <bits/stdc++.h> using i64 = long long; using namespace std; constexpr i64 inf = 1E18; i64 sq(i64 x) { return x * x; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> h(n), w(n); for (int i = 0; i < n; i++) { cin >> h[i]; } vector<i64> pre(n); for (int i = 0; i < n; i++) { cin >> w[i]; if (i > 0) pre[i] = pre[i - 1] + w[i]; } vector<i64> dp(n, inf); dp[0] = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { dp[i] = min(dp[i], dp[j] + pre[i - 1] - pre[j] + sq(h[i] - h[j])); } } cout << dp[n - 1] << "\n"; return 0; } /* 6 3 8 7 1 6 6 0 -1 9 1 2 0 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...