C++ 解法, 执行用时: 526ms, 内存消耗: 31736K, 提交时间: 2022-05-09 17:09:46

#include <cstdio>
#include <algorithm>
using namespace std;
#define dl double
#define ll long long
const int N=6e5;
int n;
struct _
{
	ll x,y;
	bool operator<(const _ b)const{ return x<b.x||(x==b.x&&y<b.y);}
}q[N],A[N],B[N]; 
int t;
ll a[N],b[N],c[N];
ll f[N];
dl e=1e-10;
dl xl(_ a,_ b){if (b.x==a.x)return 1e18;return 1.0*(b.y-a.y)/(b.x-a.x);}
int check(_ a,_ b,_ c){return xl(a,c)-xl(a,b)>=e;}
int find(int L,int R,ll k)
{
	int l=L,r=R-1,ans=R;
	while (l<=r)
	{
		int mid=l+r>>1;
		if (k>=xl(q[mid],q[mid+1]))
		ans=mid,r=mid-1;
		else
		l=mid+1;
	}
	//if (-k*q[ans].x+q[ans].y<-k*q[R].x+q[R].y)
	//ans=R;
	return ans;
}
void cdq(int l,int r)
{
	if (l==r){f[l]=max(f[l],c[l]);A[l].x=b[l],A[l].y=f[l];return;}
	int mid=l+r>>1;
	cdq(l,mid);
	int h=1,t=0;
	for (int i=l;i<=mid;++i)
	{
		while (h<t&&check(q[t-1],q[t],A[i]))t--;
		q[++t]=A[i];
	}
	int k;
	for (int i=mid+1;i<=r;++i)
	{
	k=find(h,t,-a[i]),f[i]=max(f[i],a[i]*q[k].x+q[k].y+c[i]);
	//if (l==1&&r==n)printf("ss%.0lf %.0lf %.0lf %.0lf\n",i,k,q[1].x,q[1].y);
	}
	cdq(mid+1,r);
	int q1=l,q2=mid+1,s=l;
	while (q1<=mid&&q2<=r)
	if (A[q1]<A[q2])
	B[s++]=A[q1++];
	else
	B[s++]=A[q2++];
	while (q1<=mid)B[s++]=A[q1++];
	while (q2<=r)B[s++]=A[q2++];
	for (int i=l;i<=r;++i)A[i]=B[i];
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]),f[i]=-1e18;
	cdq(1,n);
	ll ans=f[1];
	for (int i=1;i<=n;++i)ans=max(ans,f[i]);
	printf("%lld\n",ans);
}