oj.uz

Submission #54905

# Submission time Handle Problem Language Result Execution time Memory
54905 2018-07-05T10:11:58 Z istlemin Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 3004 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n;
vi h;
vi w;

int main(){
	cin.sync_with_stdio(false);
	cin>>n;
	h.resize(n);
	w.resize(n);

    rep(i,0,n)
        cin>>h[i];
    ll sumW = 0;
    rep(i,0,n){
        cin>>w[i];
        sumW += w[i];
	}
    vi dp(n,1e18);
    dp[0] = -w[0];
    rep(i,1,n){
        rep(j,0,i){
            dp[i] = min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j]));
        }
        dp[i] -= w[i];
        //cout<<dp[i]<<" ";
    }
    cout<<sumW + dp[n-1]<<endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 580 KB Output is correct
5 Correct 3 ms 592 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 580 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Execution timed out 3042 ms 3004 KB Time limit exceeded
7 Halted 0 ms 0 KB -