Submission #939030

#	Time	Username	Problem	Language	Result	Execution time	Memory
939030		vjudge1	Building Bridges (CEOI17_building)	C++17	30 / 100	3031 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++){
			
			// kx + b
			/*
			new_dp[i] = (h[i] - h[j])^2 + dp[j]
			
			(h[i] - h[j]) * (h[i] - h[j]) = kx
			
			h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j]
			*/
			new_dp[i] = min(new_dp[i], dp[j] + h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * 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