oj.uz

Submission #468986

# Submission time Handle Problem Language Result Execution time Memory
468986 2021-08-30T10:28:38 Z Josia Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3784 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")


#include <bits/stdc++.h>

#define int int64_t

using namespace std;


vector<int> pfs = {0};


vector<int> mem;


int dp(vector<pair<int, int>>& pillars, int lenght) {
    if (lenght == 0) {
        return 0;
    }
    if (mem[lenght] != 1e17) return mem[lenght];

    int res = 1e17;

    for (int i = 0; i<lenght; i++) {
        res = min(res, dp(pillars, i) + (pfs[lenght] - pfs[i+1]) + (pillars[i].first - pillars[lenght].first) * (pillars[i].first - pillars[lenght].first));
    }
    return mem[lenght] = res;
}




signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n; cin >> n;

    mem.assign(n, 1e17);


    vector<pair<int, int>> pillars(n);

    for (int i = 0; i<n; i++) {
        cin >> pillars[i].first;
    }
    for (int i = 0; i<n; i++) {
        cin >> pillars[i].second;
        pfs.push_back(pfs.back() + pillars[i].second);
    }

    pillars[0].second = 0;

    pillars.back().second = 0;


    cout << dp(pillars, n-1) << "\n";


    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

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