oj.uz

Submission #240045

# Submission time Handle Problem Language Result Execution time Memory
240045 2020-06-17T20:04:23 Z eohomegrownapps Building Bridges (CEOI17_building) C++14
30 / 100
 81 ms 27016 KB 
#include <bits/stdc++.h>
using namespace std;
typedef __int128 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*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,n-1);
	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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 27000 KB Output is correct
2 Correct 81 ms 27000 KB Output is correct
3 Correct 80 ms 27000 KB Output is correct
4 Correct 74 ms 27016 KB Output is correct
5 Correct 76 ms 27000 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -