C++14(g++5.4) 解法, 执行用时: 222ms, 内存消耗: 3540K, 提交时间: 2019-06-10 14:39:32

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[1000505];
int main()
{
    int n, m;
    ll ans=0;
    scanf("%d%d", &n, &m);
    for (int i=0;i<n;i++)
    {
        int h,v;
        scanf("%d%d",&h,&v);
        dp[h]+=v;
        ans=max(ans,dp[h]);
        for (int j=max(1,h-m);j<=h+m;j++)
            dp[j]=max(dp[j],dp[h]);
    }
    printf("%lld",ans);
}

C++ 解法, 执行用时: 245ms, 内存消耗: 680K, 提交时间: 2022-02-28 21:01:19

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll dp[N];
int main()
{
	int n,m,x,y;
	ll ans=0;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>x>>y;
		dp[x]+=y;
		ans=max(dp[x],ans);
		for(int j=max(1,x-m);j<=x+m;j++)
		{
			dp[j]=max(dp[j],dp[x]);
		}
	}
	cout<<ans<<endl;
	return 0;
}