C++14(g++5.4) 解法, 执行用时: 88ms, 内存消耗: 115424K, 提交时间: 2018-10-06 13:11:22

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v;
int getid(int x) {
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
ll x[1111],y[1111],z[1111];
ll dp[2444][2444],sumx[2444][2444],sumy[2444][2444];
int main() {
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",x+i,y+i,z+i),v.push_back(x[i]),v.push_back(y[i]);
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++)x[i]=getid(x[i]),y[i]=getid(y[i]),sumx[x[i]][y[i]]+=z[i],sumy[x[i]][y[i]]+=z[i];
    ll ans=0;
    for(int i=1;i<=v.size();i++)
        for(int j=1;j<=v.size();j++){
            sumx[i][j]+=sumx[i][j-1];
            sumy[i][j]+=sumy[i-1][j];
            dp[i][j]=max(dp[i-1][j]+sumx[i][j]*(m-v[i-1]-v[j-1]+1),dp[i][j-1]+sumy[i][j]*(m-v[i-1]-v[j-1]+1));
            if(v[i-1]+v[j-1]<=m)ans=max(ans,dp[i][j]);
        }
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 66ms, 内存消耗: 63456K, 提交时间: 2018-10-06 14:52:24

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,x[1010],y[1010],z[1010],a[2010];
long long dp[2010][2010],sum[2010][2010],ans;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d%d",x+i,y+i,z+i),a[++cnt]=x[i],a[++cnt]=y[i];
	a[++cnt]=m;sort(a+1,a+1+cnt);cnt=unique(a+1,a+1+cnt)-a-1;
	for(int i=1;i<=n;i++){
		int u=lower_bound(a+1,a+1+cnt,x[i])-a,v=lower_bound(a+1,a+1+cnt,y[i])-a;
		sum[u][v]+=z[i];
	}
	for(int i=1;i<cnt;i++)
		for(int j=1;j<cnt;j++)sum[i][j]+=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
	for(int i=1;i<cnt;i++)
		for(int j=1;j<cnt;j++){
			dp[i][j]=max(dp[i-1][j]+sum[i-1][j]*(a[i]-a[i-1]-1),dp[i][j]);
			dp[i][j]=max(dp[i][j-1]+sum[i][j-1]*(a[j]-a[j-1]-1),dp[i][j]);
			dp[i][j]+=sum[i][j];
			if(a[i]+a[j]<=m)ans=max(ans,dp[i][j]+sum[i][j]*(m-a[i]-a[j]));
			else break;
		}
	printf("%lld",ans);return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 177ms, 内存消耗: 36424K, 提交时间: 2020-07-24 02:25:48

#!/usr/bin/env python3
#
# Growth
#
import sys, os

def read_ints(): return list(map(int, input().split()))

n, m = read_ints()
a = [read_ints() for _ in range(n)]
s = {}
x, y = set(), set()
for i, j, z in a:
	if i + j > m: continue
	x.add(i)
	y.add(j)
	s[(i, j)] = s.get((i, j), 0) + z
x, y = [0] + sorted(x), [0] + sorted(y)

dp = [[0] * len(y) for _ in range(len(x))]
v = [[0] * len(y) for _ in range(len(x))]
ans = 0
for i in range(1, len(x)):
	for j in range(1, len(y)):
		v[i][j] = s.get((x[i], y[j]), 0) + v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1]
		dp[i][j] = v[i][j] + max(dp[i - 1][j] + (x[i] - x[i - 1] - 1) * v[i - 1][j], dp[i][j - 1] + (y[j] - y[j - 1] - 1) * v[i][j - 1])
		ans = max(ans, dp[i][j] + (m - x[i] - y[j]) * v[i][j])

print(ans)