基础斜率优化
首先按 (x) 从小到大把矩形排个序。由于它们不内含，(y) 一定是不增的。
设 (dp_i) 为选到第 (i) 个矩形且第 (i) 个必须选时最大的权值。
[dp_i = max(dp_j + y_i imes (x_i - x_j)) - c_i
]
可以化成：
[dp_i = max(dp_j - y_i x_j) - c_i + x_i y_i
]
就可以斜率优化了。
注意：
1.这里斜率被取反了（(-a[i].x) 变成 (a[i].x)），相应地 (bad) 里的符号也要改变。
2.除法记得两边同时强制转化为 (double) ，不要像我一样 (WA) (56) 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const ll inf=0x3f3f3f3f3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
void chmax(ll &x,ll y){if(x < y) x = y;}
void chmin(int &x,int y){if(x > y) x = y;}
ll n,dp[1000005];
struct rect{
ll x,y,cost;
}a[1000005];
struct point{
ll x,y,id;
};
bool cmp(rect x,rect y){return x.x < y.x;}
bool bad(point a,point b,point c){
double x = (double)(b.y - a.y) / (b.x - a.x), y = (double)(c.y - b.y) / (c.x - b.x);
return x < y;
}
int top;point s[1000010];
void read(ll &x){
x=0;
char c = getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x = 10 * x + (c^48),c = getchar();
}
int main()
{
read(n);
rep(i,1,n) read(a[i].x),read(a[i].y),read(a[i].cost);
sort(a+1,a+n+1,cmp);
int gt = 1;
s[++top] = (point){0, 0, 0};
rep(i,1,n) {
dp[i] = -inf;
//rep(j,0,i-1) chmax(dp[i], dp[j] + a[i].y * (a[i].x - a[j].x) - a[i].cost);
while(gt < top && dp[s[gt].id] + a[i].y * (a[i].x - a[s[gt].id].x) - a[i].cost < dp[s[gt+1].id] + a[i].y * (a[i].x - a[s[gt+1].id].x) - a[i].cost) gt++;
dp[i] = dp[s[gt].id] + a[i].y * (a[i].x - a[s[gt].id].x) - a[i].cost;
point u = (point){a[i].x, dp[i], i};
while(top > 1 && bad(s[top-1], s[top], u)) top--;
//cout<<s[gt].id<<endl;
s[++top] = u;
}
ll ans = 0;
rep(i,1,n) ans = max(ans, dp[i]);
cout<<ans<<endl;
return 0;
}