제출 #66737

#제출 시각아이디문제언어결과실행 시간메모리
66737AbelyanBuilding Bridges (CEOI17_building)C++17
30 / 100
3043 ms2736 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...