Submission #961759

#	Time	Username	Problem	Language	Result	Execution time	Memory
961759		LucaIlie	Building Bridges (CEOI17_building)	C++17	30 / 100	3051 ms	3084 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
int h[MAX_N];
long long 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[i - 1] - w[j] + (long long)(h[i] - h[j]) * (h[i] - h[j]) );
    }

    cout << dp[n - 1];

    return 0;
}

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