Submission #934231

#	Time	Username	Problem	Language	Result	Execution time	Memory
934231		UmairAhmadMirza	Building Bridges (CEOI17_building)	C++14	30 / 100	3080 ms	3680 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e5+5;
int const inf=1e18+5;
int H[N],W[N],dp[N];
signed main() 
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>H[i];
  for(int i=1;i<=n;i++){
    cin>>W[i];
    W[i]+=W[i-1];
  }
  for(int i=2;i<=n;i++){
    dp[i]=inf;
    for(int j=1;j<i;j++){
      int v=abs(H[i]-H[j]);
      v*=v;
      v+=dp[j]+(W[i-1]-W[j]);
      dp[i]=min(dp[i],v);
    }
  }
  cout<<dp[n]<<endl;
  return 0;
}

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