Submission #1239996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239996		yenthuya	Building Bridges (CEOI17_building)	C++20	30 / 100	3094 ms	3400 KiB

building

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    
    vector<ll> h(n), w(n), prefix(n+1, 0), dp(n, LLONG_MAX);

    for (int i = 0; i < n; ++i)
        cin >> h[i];

    for (int i = 0; i < n; ++i) {
        cin >> w[i];
        prefix[i+1] = prefix[i] + w[i];  // Prefix sum của w
    }

    dp[0] = 0; // Chi phí tại trụ đầu tiên là 0

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            ll remove_cost = prefix[i] - prefix[j+1]; // Chi phí gỡ các trụ giữa j và i
            ll build_cost = (h[i] - h[j]) * (h[i] - h[j]);
            dp[i] = min(dp[i], dp[j] + build_cost + remove_cost);
        }
    }

    cout << dp[n-1] << endl;
    return 0;
}

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