# 5873. 小p的属性

xiaoxiao2021-03-01  26

## 程序：

#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #define N 2005 #define LL long long using namespace std; struct data{LL x,y,z;}x[N]; LL sum[N][N],f[N][N],b[N]; LL n,m,size,cnt; int main(){ freopen("growth.in","r",stdin); freopen("growth.out","w",stdout); scanf("%lld%lld",&n,&m); for (int i=1;i<=n;i++) { scanf("%lld%lld%lld",&x[i].x,&x[i].y,&x[i].z); } for (int i=1;i<=n;i++) b[++cnt]=x[i].x,b[++cnt]=x[i].y; sort(b+1,b+cnt+1); size=unique(b+1,b+cnt+1)-b-1; for (int i=1;i<=n;i++){ x[i].x=lower_bound(b+1,b+size+1,x[i].x)-b; x[i].y=lower_bound(b+1,b+size+1,x[i].y)-b; sum[x[i].x][x[i].y]+=x[i].z; } for (int i=1;i<=size;i++) for (int j=1;j<=size;j++){ sum[i][j]=sum[i-1][j]+sum[i][j-1]+sum[i][j]-sum[i-1][j-1]; } for (int i=1;i<=size;i++) for (int j=1;j<=size;j++){ if (i==1&&j==1) continue; f[i][j]=max(f[i-1][j]+sum[i-1][j]*(b[i]-b[i-1]-1),f[i][j-1]+sum[i][j-1]*(b[j]-b[j-1]-1))+sum[i][j]; } LL ans=0; for (int i=1;i<=size;i++) for (int j=1;j<=size;j++) if (b[i]+b[j]<=m){ ans=max(ans,f[i][j]+sum[i][j]*(m-b[i]-b[j])); } printf("%lld\n",ans); }