제출 #468982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468982		wdjpng	Building Bridges (CEOI17_building)	C++17	30 / 100	55 ms	1740 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++)
#define per(i,n) for(int i = n-1; i >= 0; 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;
        per(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: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40