Submission #976968

#TimeUsernameProblemLanguageResultExecution timeMemory
976968duckindogBuilding Bridges (CEOI17_building)C++17
30 / 100
3036 ms3212 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int n; int h[N], w[N]; int d[N]; long long f[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> h[i]; for (int i = 1; i <= n; ++i) cin >> w[i]; for (int i = 1; i <= n; ++i) d[i] = d[i - 1] + w[i]; memset(f, 40, sizeof f); f[1] = 0; for (int i = 1; i <= n; ++i) { auto& ret = f[i]; for (int j = 1; j < i; ++j) ret = min(ret, f[j] + 1ll * (h[i] - h[j]) * (h[i] - h[j]) + d[i - 1] - d[j]); } cout << f[n] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...