题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1218

思路：虽说题目类型是DP，但是被我很无耻地前缀和+暴力枚举过了。。。。（这数据）

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std;

 

#define MAXN 5003

 

int f[MAXN][MAXN];

int n,r;

int maxx=0,maxy=0;

int ans=0;

int sum=0;

 

void getint(int &x){

    int c=getchar();

    while (c>int('9')||c<int('0')) c=getchar();

    x=c-int('0');

    while (1){

        c=getchar();

        if (c>=int('0')&&c<=int('9')) x*=10,x+=(c-int('0'));

        else break;

    }

}

 

void putint(int x){

    int ans[100];

    ans[0]=0;

    while (x) ans[++ans[0]]=x%10,x/=10;

    for (int i=ans[0];i>0;i--) putchar(int('0')+ans[i]);

    putchar(int('\n'));

}

 

int main(){

    memset(f,0,sizeof(f));

    getint(n);

    getint(r);

    for (int i=0;i++<n;){

        int x,y,v;

        getint(x);

        getint(y);

        getint(v);

        x++,y++;

        maxx=max(maxx,x);

        maxy=max(maxy,y);

        f[x][y]=v;

        sum+=v;

    }

    for (int i=0;i++<maxx;){

        for (int j=0;j++<maxy;){

            f[i][j]+=f[i-1][j];

            f[i][j]-=f[i-1][j-1];

            f[i][j]+=f[i][j-1];

        }

    }

    for (int i=r;i++<maxx;){

        for (int j=r;j++<maxy;){

            int x=f[i][j];

            x-=f[i-r][j];

            x-=f[i][j-r];

            x+=f[i-r][j-r];

            ans=max(ans,x);

        }

    }

    if (r>=maxx&&r>=maxy){

        ans=f[maxx][maxy];

    } else {

        if (r>=maxx){

            for (int j=r-1;j++<maxy;){

                ans=max(ans,f[maxx][j]-f[maxx][j-r]);

            }

        }

        if (r>=maxy){

            for (int j=r-1;j++<maxx;){

                ans=max(ans,f[j][maxy]-f[j-r][maxy]);

            }

        }

    }

    putint(ans);

    return 0;

}