Submission #961761

#	Time	Username	Problem	Language	Result	Execution time	Memory
961761		LucaIlie	Building Bridges (CEOI17_building)	C++17	30 / 100	3043 ms	2712 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
long long h[MAX_N], w[MAX_N], dp[MAX_N];

int main() {
    int n;

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

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

    cout << dp[n - 1];

    return 0;
}

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