oj.uz

Submission #66737

# Submission time Handle Problem Language Result Execution time Memory
66737 2018-08-12T08:23:49 Z Abelyan Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 2736 KB 
#include <iostream>
using namespace std;

typedef long long ll;
const int N = 100006;
const long long INF = (ll)1000000000000000007;
int h[N], w[N], dp[N];

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i<n; i++) {
		cin >> h[i];
	}
	for (int i = 0; i<n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i<n; i++) {
		ll sum = 0;
		ll mn = INF;
		for (int j = i - 1; j >= 0; j--) {
			if (sum + dp[j] + (h[j] - h[i])*(h[j] - h[i])<mn) {
				mn = sum + dp[j] + (h[j] - h[i])*(h[j] - h[i]);

			}
			sum += w[j];
		}
		dp[i] = mn;
	}
	cout << dp[n - 1] << endl;
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 5 ms 608 KB Output is correct
5 Correct 4 ms 608 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 5 ms 608 KB Output is correct
5 Correct 4 ms 608 KB Output is correct
6 Execution timed out 3043 ms 2736 KB Time limit exceeded
7 Halted 0 ms 0 KB -