oj.uz

Submission #961761

# Submission time Handle Problem Language Result Execution time Memory
961761 2024-04-12T12:13:17 Z LucaIlie Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 2712 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2488 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 2712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2488 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Execution timed out 3043 ms 2712 KB Time limit exceeded
7 Halted 0 ms 0 KB -