Submission #468981

#	Time	Username	Problem	Language	Result	Execution time	Memory
468981		wdjpng	Building Bridges (CEOI17_building)	C++17	0 / 100	57 ms	1868 KiB

building

#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)

using namespace std;

int n;

int bruteforce(vector<int>h, vector<int>w)
{
    vector<int>dp(n, 1e18);
    vector<int>pref(n);
    pref[0] = w[0];
    for(int i = 1; i < n; i++) {pref[i]=w[i]; pref[i]+=pref[i-1];}

    dp[0] = 0;
    rep(i,n)
    {
        int sum = 0;
        rep(j,i)
        {   
            int delh = h[i]-h[j];
            dp[i]=min(dp[i], dp[j]+sum+delh*delh);
            sum+=w[j];
        }
    }
    return dp[n-1];
}

signed main()
{
    cin >> n;

    vector<int>h(n),w(n);
    rep(i,n) cin>>h[i];
    rep(i,n) cin>>w[i];
    if(n<=1000) cout<<bruteforce(h,w)<<"\n";
}

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