oj.uz

Submission #468978

# Submission time Handle Problem Language Result Execution time Memory
468978 2021-08-30T10:12:31 Z wdjpng Building Bridges (CEOI17_building) C++17
0 / 100
 55 ms 1848 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)

using namespace std;

int n;

int bruteforce(vector<int>h, vector<int>w)
{
    vector<int>dp(n, 1e18);
    vector<int>pref(n);
    pref[0] = w[0];
    for(int i = 1; i < n; i++) {pref[i]=w[i]; pref[i]+=pref[i-1];}
    dp[0] = w[0];

    rep(i,n)
    {
        rep(j,i)
        {   
            int delh = h[i]-h[j];
            dp[i]=min(dp[i], dp[j]+pref[i-1]-pref[j]+delh*delh);
        }
    }
    return dp[n-1];
}

signed main()
{
    cin >> n;

    vector<int>h(n),w(n);
    rep(i,n) cin>>h[i];
    rep(i,n) cin>>w[i];
    if(n<=1000) cout<<bruteforce(h,w)<<"\n";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 1848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -