제출 #1011374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011374		NValchanov	Building Bridges (CEOI17_building)	C++17	30 / 100	3027 ms	5212 KiB

building

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const ll MAXH = 1e6 + 10;
const ll MAXW = 1e6 + 10;
const ll INF = 4e18 + 10;

int n;
ll h[MAXN];
ll w[MAXN];
ll prefw[MAXN];
ll dp[MAXN][2];

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
        prefw[i] = prefw[i - 1] + w[i];
        dp[i][0] = dp[i][1] = INF;
    }
}

ll query(ll left, ll right)
{
    if(left > right)
        return 0LL;

    return prefw[right] - prefw[left - 1];
}

void solve()
{
    dp[1][0] = dp[1][1] = 0;

    for(int i = 2; i <= n; i++)
    {
        dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + w[i];

        for(int j = i - 1; j >= 1; j--)
        {
            dp[i][1] = min(dp[i][1], dp[j][1] + query(j + 1, i - 1) + (h[i] - h[j]) * (h[i] - h[j]));
        }
    }

    cout << dp[n][1] << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();

    return 0;
}

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