Submission #66737

#	Time	Username	Problem	Language	Result	Execution time	Memory
66737		Abelyan	Building Bridges (CEOI17_building)	C++17	30 / 100	3043 ms	2736 KiB

building

#include <iostream>
using namespace std;

typedef long long ll;
const int N = 100006;
const long long INF = (ll)1000000000000000007;
int h[N], w[N], dp[N];

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i<n; i++) {
		cin >> h[i];
	}
	for (int i = 0; i<n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i<n; i++) {
		ll sum = 0;
		ll mn = INF;
		for (int j = i - 1; j >= 0; j--) {
			if (sum + dp[j] + (h[j] - h[i])*(h[j] - h[i])<mn) {
				mn = sum + dp[j] + (h[j] - h[i])*(h[j] - h[i]);

			}
			sum += w[j];
		}
		dp[i] = mn;
	}
	cout << dp[n - 1] << endl;
	return 0;
}

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