oj.uz

Submission #939054

# Submission time Handle Problem Language Result Execution time Memory
939054 2024-03-06T04:35:52 Z vjudge1 Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3420 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;

const int inf = 1e9 + 50;
struct Line{
	int k, b;
	Line(int k = 0, int b = 0) : k(k), b(b) {}
};

int F(Line &a, int x){
	return a.k*x + a.b;
}
struct LiChao{
	struct Node{
		Line k;
		Node *l, *r;
		Node(){
			l = nullptr, r = nullptr;
		}
	};
	int n;
	Node *root;
	LiChao(int n) : n(n), root(nullptr) {}
	void addLine(Node *&p, int l, int r, Line &a){
		if(!p) p = new Node();	
		int mid = (l + r) / 2;
		int l_side = F(a, l) > F(p->k, l);
		int m_side = F(a, mid) > F(p->k, mid);
		if(m_side) p->k = a;
		if(l == r-1) return;
		if(l_side == m_side){
			addLine(p->r, mid, r, a);
		}else{
			addLine(p->l, l, mid, a);
		}
	}
	void addLine(Line a){
		addLine(root, 0, n, a);
	}
	int get(Node *&p, int l, int r, int x){
		if(!p) return 0LL;
		if(l == r-1){
			return F(p->k, x);
		}
		int mid = (l + r) / 2;
		if(mid > x){
			return max(F(p->k, x), get(p->l, l, mid, x));
		}else{
			return max(F(p->k, x), get(p->r, mid, r, x));
		}
	}
	
	int get(int x){
		return get(root, 0, n, x);
	}
	
};
/*
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];
	}
	LiChao lch(inf);
	lch.addLine(Line(0, 0));
	vector<int> dp(n+1, mod);
	dp[0] = 0;
	dp[1] = 0;
	lch.addLine(Line(h[1], dp[1] + w[1] + h[1] * h[1]));
	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] - w[j] + h[j] * h[j] - (h[i] * h[j] + h[j] * h[i]) + w[i-1] + h[i] * h[i]);
		}
		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 0 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 3420 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 0 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Execution timed out 3059 ms 3420 KB Time limit exceeded
7 Halted 0 ms 0 KB -