제출 #1184073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184073		belgianbot	Building Bridges (CEOI17_building)	C++20	30 / 100	3094 ms	10568 KiB

building

#include <bits/stdc++.h>
#define int long long

using namespace std;

vector<int> memo, cost, h;
int N;

int dp(int i) {
    if (i == N) return LLONG_MAX;
    if (i == N - 1) return 0;

    if (memo[i] != -1) return memo[i];

    int sum = 0;
    int res = LLONG_MAX;
    for (int j = i+1; j < N; j++) {
        res = min(res, dp(j) + sum + (h[i] - h[j]) * (h[i] - h[j]));
        sum += cost[j];
    }
    return memo[i] = res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    memo.resize(N, -1); cost.resize(N); h.resize(N);
    
    for (int i = 0; i < N; i++) cin >> h[i];
    for (int i = 0; i < N; i++) cin >> cost[i];

    cout << dp(0);

    return 0;
}

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