제출 #1196787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196787		justarandomguy	Building Bridges (CEOI17_building)	C++20	100 / 100	43 ms	12616 KiB

building

#include <iostream>
using namespace std;
#define ll long long
#define ld long double
const int N=1e5+100;
const ll inf=1e18;
ll dp[N],a[N],pre[N],h[N],w[N];
struct line
{
	ll m=0,c=inf;
	line(){} // change base case if want max
	line(ll m_,ll c_): m(m_),c(c_){}
	ll get(ll x)
	{
		return m*x+c;
	}
};
struct LiChao
{
	line cb; // cur best
	int s,e; // 1e6+20
	LiChao* next[2];
	LiChao(int x,int y)
	{
		s=x,e=y;
	}
	void insert(line cur) // query min have to change for query max
	{
		// if((e-s)>1e6)
		// {
			// cout<<"At node "<<s<<' '<<e<<endl;
			// cout<<"Inserting line "<<cur.m<<' '<<cur.c<<endl;
		// }
		int mid=(s+e)/2;
		bool cl=cur.get(s) < cb.get(s);
		bool cm=cur.get(mid) < cb.get(mid);
		if(cm)
		{
			// cout<<"getting better mid swapping"<<endl;
			swap(cb,cur);
		}
		if(s==e)return;
		// cout<<"Continueing "<<endl;
		int p=(cl==cm);
		if(next[p]==NULL)
		{
			if(p==0)
				next[p]=new LiChao(s,mid);
			else
				next[p]=new LiChao(mid+1,e);
		}
		// change for right now inserting original cb
		next[p]->insert(cur);
		// if(cl==cm)
		// {
		// 	// both 1 
		// 	// both 0
		// 	if(next[1]==NULL)
		// 		next[1]=new LiChao(s,mid);
		// 	next[1]->insert(cur);
		// }
		// else
		// {
		// 	if(next[0]==NULL)
		// 		next[0]=new LiChao(s,mid);
		// 	next[0]->insert(cur);
		// }
	}
	ll get(ll x)
	{
		ll mx=cb.get(x);
		if(s==e)
			return mx;
		int mid=(s+e)/2;
		if(next[x>mid]!=NULL)
			mx=min(mx,next[x>mid]->get(x));
		return mx;
	}
};
void solve()
{
	LiChao* root=new LiChao(0,1e6+2);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	for(int i=1;i<=n;i++)
		cin>>w[i];
	for(int i=1;i<=n;i++)
		pre[i]=pre[i-1]+w[i];
	for(int i=1;i<=n;i++)
		dp[i]=1e18;
	dp[1]=0;
	root->insert(line(h[1]*-2,dp[1]-pre[1]+h[1]*h[1]));
	for(int i=2;i<=n;i++)
	{
		dp[i]=pre[i-1]+(h[i]*h[i])+root->get(h[i]);
		root->insert(line(h[i]*-2,dp[i]-pre[i]+h[i]*h[i]));
	}
	cout<<dp[n];
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int t=1;
	while(t--)
	{
		solve();
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40