oj.uz

Submission #939030

# Submission time Handle Problem Language Result Execution time Memory
939030 2024-03-06T03:50:03 Z vjudge1 Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3412 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
#define int long long
const int mod = 1e16;


/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/
signed main(){
	int n; cin >> n;
	vector<int> h(n+1);
	for(int i = 1;i <= n; i++) cin >> h[i];
	vector<int> w(n+1, 0);
	for(int i = 1;i <= n; i++){
		cin >> w[i];
		w[i]+= w[i-1];
	}
	
	auto get=[&](int l, int r){
		if(l > r) return 0LL;
		return w[r] - w[l-1];
	};
	vector<int> dp(n+1, mod);
	dp[0] = 0;
	dp[1] = 0;
	for(int i = 2;i <= n; i++){
		vector<int> new_dp = dp;
		for(int j = 1;j < i; j++){
			
			// kx + b
			/*
			new_dp[i] = (h[i] - h[j])^2 + dp[j]
			
			(h[i] - h[j]) * (h[i] - h[j]) = kx
			
			h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j]
			*/
			new_dp[i] = min(new_dp[i], dp[j] + h[i] * h[i] - h[i] * h[j] - h[j] * h[i] + h[j] * h[j] + get(j+1, i-1));
		}
		swap(dp, new_dp);
	}
	cout << dp[n];
	return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Execution timed out 3031 ms 3412 KB Time limit exceeded
7 Halted 0 ms 0 KB -