Submission #166591

#	Time	Username	Problem	Language	Result	Execution time	Memory
166591		thiago4532	Building Bridges (CEOI17_building)	C++17	30 / 100	3029 ms	4360 KiB

building

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 1e5 + 10;
int h[maxn], pref[maxn], w[maxn];
int n, dp[maxn];

int32_t main() {
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> h[i];

	for(int i=1;i<=n;i++)
		cin >> w[i], pref[i] = pref[i-1] + w[i];

	dp[1] = 0;
	for(int i=2;i<=n;i++) {
		dp[i] = 0x3f3f3f3f3f3f3f3f;
		for(int j=1;j<i;j++) {
			dp[i] = min(dp[i], dp[j] - pref[j] + h[j]*h[j] - 2*h[j] * h[i]);
		}
		dp[i] += h[i]*h[i] + pref[i-1];
	}
	cout << dp[n] << "\n";
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40