Submission #606927

#	Time	Username	Problem	Language	Result	Execution time	Memory
606927		pakhomovee	Building Bridges (CEOI17_building)	C++17	30 / 100	3051 ms	4580 KiB

building

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define int long long
const int inf = 1e18;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> h(n);
    for (int& i : h) cin >> i;
    vector<int> w(n);
    for (int& i : w) cin >> i;
    vector<int> dp(n, inf);
    dp[0] = 0;
    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + w[i - 1];
    for (int i = 1; i < n; ++i) {
        for (int j = i - 1; j >= 0; --j) {
            dp[i] = min(dp[i], (dp[j] - pref[j + 1] + h[j] * h[j]) - (2 * h[j] * h[i]) + (h[i] * h[i] + pref[i]));
        }
    }
    cout << dp.back();
}

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