oj.uz

Submission #240047

# Submission time Handle Problem Language Result Execution time Memory
240047 2020-06-17T20:06:31 Z eohomegrownapps Building Bridges (CEOI17_building) C++14
100 / 100
 209 ms 129248 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll INF = 1e18;
struct Line{
	ll m,c;
	Line(ll _m, ll _c){
		m=_m;c=_c;
	}
	ll operator()(ll x){
		return m*x+c;
	}
};

struct Node{
	ll s,e,m;
	Line f = Line(0,INF);
	Node *l, *r;

	Node(ll _s, ll _e){
		s=_s;e=_e;
		if (s==e){return;}
		m=(s+e)/2;
		l = new Node(s,m);
		r = new Node(m+1,e);
	}

	void insert(Line ins){
		if (s==e){
			if (ins(s)<f(s)){
				f=ins;
			}
			return;
		}
		if (ins.m==f.m){
			if (ins.c<f.c){
				f=ins;
			}
			return;
		}
		//wlog insert line has higher gradient
		if (ins.m<f.m){
			swap(ins,f);
		}
		if (ins(m)<f(m)){
			r->insert(f);
			f=ins;
		} else {
			l->insert(ins);
		}
	}

	ll query(ll x){
		if (s==e){
			return f(x);
		}
		if (x<=m){
			return min(f(x),l->query(x));
		} else {
			return min(f(x),r->query(x));
		}
	}
};

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll n;
	int nv;
	cin>>nv;
	n=nv;
	vector<ll> h(n);
	vector<ll> pref(n+1);
	for (ll i = 0; i<n; i++){
		long long tmp;
		cin>>tmp;
		h[i]=tmp;
	}
	for (ll i = 0; i<n; i++){
		long long tmp;
		cin>>tmp;
		pref[i+1]=tmp;
		pref[i+1]+=pref[i];
	}
	vector<ll> dp(n);
	Node *lichao = new Node(0,1000000);
	lichao->insert(Line(-2*h[0],dp[0]-pref[1]+h[0]*h[0]));
	for (ll x = 1; x<n; x++){
		ll minval = lichao->query(h[x]);
		dp[x]=h[x]*h[x]+pref[x]+minval;
		lichao->insert(Line(-2*h[x],dp[x]-pref[x+1]+h[x]*h[x]));
	}
	cout<<(long long)(dp[n-1])<<'\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 125564 KB Output is correct
2 Correct 126 ms 125560 KB Output is correct
3 Correct 106 ms 125560 KB Output is correct
4 Correct 105 ms 125560 KB Output is correct
5 Correct 105 ms 125560 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 127864 KB Output is correct
2 Correct 157 ms 127996 KB Output is correct
3 Correct 176 ms 127992 KB Output is correct
4 Correct 151 ms 127992 KB Output is correct
5 Correct 153 ms 128044 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 125564 KB Output is correct
2 Correct 126 ms 125560 KB Output is correct
3 Correct 106 ms 125560 KB Output is correct
4 Correct 105 ms 125560 KB Output is correct
5 Correct 105 ms 125560 KB Output is correct
6 Correct 164 ms 127864 KB Output is correct
7 Correct 157 ms 127996 KB Output is correct
8 Correct 176 ms 127992 KB Output is correct
9 Correct 151 ms 127992 KB Output is correct
10 Correct 153 ms 128044 KB Output is correct
11 Correct 209 ms 129248 KB Output is correct
12 Correct 199 ms 129016 KB Output is correct
13 Correct 153 ms 129016 KB Output is correct
14 Correct 201 ms 129196 KB Output is correct
15 Correct 148 ms 128868 KB Output is correct
16 Correct 152 ms 128992 KB Output is correct
17 Correct 133 ms 129068 KB Output is correct
18 Correct 140 ms 129012 KB Output is correct