oj.uz

Submission #939056

# Submission time Handle Problem Language Result Execution time Memory
939056 2024-03-06T04:43:22 Z vjudge1 Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3796 KB 
#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;
	vector<int> md;
	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.clear();
			md.pb(i);
		}
		else if(tmp==res){
			md.pb(i);
		}
	}
	if(md.size()==0) return res;
	for(auto it: md){
		res=min(res,f(l,it)+f(it,r));
	}
	return res;
}
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];
	vector<int> dp(n+1,INF);
	dp[1]=0;
	
	for(int i=2;i<=n;i++){
		int k=0;
		for(int j=i-1;j>=1;j--){
			dp[i]=min(dp[i],dp[j]+k+(h[j]-h[i])*(h[j]-h[i]));
			k+=c[j];
		}
	}
	cout<<dp[n]<<endl;
	/*for(int i=1;i<=n;i++)
		cout<<dp[i]<<' ';
	cout<<endl;*/
	cerr<<f(1,n);
}
main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3047 ms 3796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Execution timed out 3047 ms 3796 KB Time limit exceeded
7 Halted 0 ms 0 KB -