oj.uz

Submission #468982

# Submission time Handle Problem Language Result Execution time Memory
468982 2021-08-30T10:17:45 Z wdjpng Building Bridges (CEOI17_building) C++17
30 / 100
 55 ms 1740 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++)
#define per(i,n) for(int i = n-1; i >= 0; 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] = 0;
    rep(i,n)
    {
        int sum = 0;
        per(j,i)
        {   
            int delh = h[i]-h[j];
            dp[i]=min(dp[i], dp[j]+sum+delh*delh);
            sum+=w[j];
        }
    }
    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
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 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 1740 KB Output isn't correct
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 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Incorrect 55 ms 1740 KB Output isn't correct
7 Halted 0 ms 0 KB -