Submission #1305607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305607		neonglitch	Building Bridges (CEOI17_building)	C++20	100 / 100	67 ms	65400 KiB

building

#include <iostream>
using namespace std;
typedef long long ll;
#define int long long
const int N=1e5+10,M=1e6+1;
const ll inf=1e18;
int h[N],dp[N],pre[N];
struct line{
	ll m,c;
	line(): m(0),c(inf){}
	line(ll q,ll s): m(q),c(s){}
	ll f(ll x)
	{
		return m*x+c;
	}
	ll inter(line& a)
	{
		return (a.c-c)/(m-a.m);
	}
};
line seg[4*M];
void add(line cur,int l=0,int r=M-1,int v=1)
{
	// cout<<"at "<<cur.m<<' '<<cur.c<<' '<<l<<' '<<r<<' '<<v<<endl;
	int m=(l+r)>>1;
	bool le=(seg[v].f(l) > cur.f(l));
	bool md=(seg[v].f(m) > cur.f(m));
	if(md)swap(cur,seg[v]);
	if(l==r)return;
	if(le!=md)
	{
		// intersect ion range [l,m]
		add(cur,l,m,2*v);
	}
	else{
		add(cur,m+1,r,2*v+1);
	}
}
ll get(int x,int l=0,int r=M-1,int v=1)
{
	if(l==r)
	{
		return seg[v].f(x);
	}
	int m=(l+r)/2;
	if(x<=m)
		return min(seg[v].f(x),get(x,l,m,2*v));
	return min(seg[v].f(x),get(x,m+1,r,2*v+1));
}
main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>pre[i];
		pre[i]+=pre[i-1];
	}
	dp[1]=0;
	add(line(-2*h[1],dp[1]-pre[1]+h[1]*h[1]));
	for(int i=2;i<=n;i++)
	{
		dp[i]=get(h[i])+pre[i-1]+(h[i]*h[i]);
		line cur(-2*h[i],dp[i]-pre[i]+h[i]*h[i]);
		add(cur);
	}
	cout<<dp[n]<<endl;
}

Compilation message (stderr)

building.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~

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