oj.uz

Submission #173108

# Submission time Handle Problem Language Result Execution time Memory
173108 2020-01-03T11:21:11 Z dvdg6566 Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 3620 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ld> vi;
typedef pair<ld,ld> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define All(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second

const ll MAXN = 1e6+10;
ll N,H[MAXN], E[MAXN];
ll W;
ll dp[MAXN];

int main(){
	cin>>N;
	for (ll i=1;i<=N;++i)cin>>H[i];
	for (ll i=1;i<=N;++i)cin>>E[i], W += E[i];
	dp[1] = -E[1];
	
	for (int i=2;i<=N;++i){
		dp[i] = 1e9;
		for (int j=1;j<i;++j){
			dp[i] = min(dp[i], dp[j] + (H[j] - H[i]) * (H[j] - H[i]) - E[i]);
		}
	}
	cout<<dp[N] + W;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 3620 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 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Execution timed out 3029 ms 3620 KB Time limit exceeded
7 Halted 0 ms 0 KB -