oj.uz

Submission #961759

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 3084 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Execution timed out 3051 ms 3084 KB Time limit exceeded
7 Halted 0 ms 0 KB -