oj.uz

Submission #45951

# Submission time Handle Problem Language Result Execution time Memory
45951 2018-04-16T14:25:12 Z sorry_Benq Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3392 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int w[100005];
ll h[100005];
ll dp[100005];
ll res = 0;
int main(){
	int N; cin >> N;
	for (int i = 0; i < N; i++){
		cin >> h[i];
	}
	for (int i = 0; i < N; i++){
		cin >> w[i];
		res += w[i];
		w[i] = -w[i];
	}
	dp[0] = w[0];
	for (int i = 1; i < N; i++){
		dp[i] = 1e16;
		for (int j = 0; j < i; j++){
			dp[i] = min(dp[j] + w[i] + (h[i] - h[j])*(h[i] - h[j]), dp[i]);
		}
	}
	cout << res + 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 488 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 4 ms 620 KB Output is correct

Subtask #2
0 / 30.0

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