Submission #1240000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240000		yenthuya	Building Bridges (CEOI17_building)	C++20	0 / 100	3095 ms	4076 KiB

building

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

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    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];
    }

    dp[0] = 0;

    // TreeMap for height -> dp value (optimized step)
    map<ll, ll> min_dp_for_height;
    min_dp_for_height[h[0]] = 0;

    for (int i = 1; i < n; ++i) {
        for (auto& [hj, dpj] : min_dp_for_height) {
            // Tính chi phí khi chọn trụ j để nối đến i
            ll cost = dpj + (h[i] - hj) * (h[i] - hj) + prefix[i] - prefix[&hj - &h[0] + 1];
            dp[i] = min(dp[i], cost);
        }

        // Cập nhật bản đồ chi phí tối ưu với h[i]
        if (!min_dp_for_height.count(h[i])) {
            min_dp_for_height[h[i]] = dp[i];
        } else {
            min_dp_for_height[h[i]] = min(min_dp_for_height[h[i]], dp[i]);
        }
    }

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

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