Submission #54905

#	Time	Username	Problem	Language	Result	Execution time	Memory
54905		istlemin	Building Bridges (CEOI17_building)	C++14	30 / 100	3042 ms	3004 KiB

building

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n;
vi h;
vi w;

int main(){
	cin.sync_with_stdio(false);
	cin>>n;
	h.resize(n);
	w.resize(n);

    rep(i,0,n)
        cin>>h[i];
    ll sumW = 0;
    rep(i,0,n){
        cin>>w[i];
        sumW += w[i];
	}
    vi dp(n,1e18);
    dp[0] = -w[0];
    rep(i,1,n){
        rep(j,0,i){
            dp[i] = min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j]));
        }
        dp[i] -= w[i];
        //cout<<dp[i]<<" ";
    }
    cout<<sumW + dp[n-1]<<endl;
}

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