Submission #939037

#	Time	Username	Problem	Language	Result	Execution time	Memory
939037		vjudge1	Building Bridges (CEOI17_building)	C++17	0 / 100	41 ms	1172 KiB

building

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define fr first
#define sc second
const long long INF=1e17,N=2e5+6;
int h[N],c[N];
int f(int l, int r){
	int val=(h[r]-h[l])*(h[r]-h[l]);
	for(int i=l+1;i<r;i++)
		val+=c[i];
	int res=val, md=-1;
	int sum=res-(h[r]-h[l])*(h[r]-h[l]);
	for(int i=l+1;i<r;i++){
		int tmp=(sum-c[i]+(h[l]-h[i])*(h[l]-h[i])+
						  (h[r]-h[i])*(h[r]-h[i]));
		if(tmp<res){
			res=tmp;
			md=i;
		}
	}
	if(md==-1) return res;
	return f(l,md)+f(md,r);
}
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	for(int i=1;i<=n;i++)
		cin>>c[i];
	int v=(h[n]-h[1])*(h[n]-h[1]);
	for(int i=2;i<n;i++)
		v+=c[i];
	cout<<f(1,n);
}
main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message (stderr)

building.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~

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