oj.uz

Submission #606927

# Submission time Handle Problem Language Result Execution time Memory
606927 2022-07-26T09:58:38 Z pakhomovee Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 4580 KB 
#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.0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Execution timed out 3051 ms 4580 KB Time limit exceeded
7 Halted 0 ms 0 KB -