Submission #939024

#	Time	Username	Problem	Language	Result	Execution time	Memory
939024		vjudge1	Building Bridges (CEOI17_building)	C++17	30 / 100	3056 ms	3412 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
#define int long long
const int mod = 1e16;


/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
signed main(){
	int n; cin >> n;
	vector<int> h(n+1);
	for(int i = 1;i <= n; i++) cin >> h[i];
	vector<int> w(n+1, 0);
	for(int i = 1;i <= n; i++){
		cin >> w[i];
		w[i]+= w[i-1];
	}
	
	auto get=[&](int l, int r){
		if(l > r) return 0LL;
		return w[r] - w[l-1];
	};
	vector<int> dp(n+1, mod);
	dp[0] = 0;
	dp[1] = 0;
	for(int i = 2;i <= n; i++){
		vector<int> new_dp = dp;
		for(int j = 1;j < i; j++){
			new_dp[i] = min(new_dp[i], dp[j] + (h[i]-h[j]) * (h[i] - h[j]) + get(j+1, i-1));
		}
		swap(dp, new_dp);
	}
	cout << dp[n];
	return 0;
}

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