这题贼煞笔。感觉一早上都在做煞笔题。
一开始想写二维树状数组。。其实直接用二维前缀就行。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int sum[5100][5100]; int main() { int n,r,x,y,z; scanf("%d%d",&n,&r); for(int i=1;i<=n;i++) scanf("%d%d%d",&x,&y,&z), sum[x+1][y+1]+=z; for(int i=1;i<=5001;i++) for(int j=1;j<=5001;j++) sum[i][j]+=sum[i-1][j]; for(int i=1;i<=5001;i++) for(int j=1;j<=5001;j++) sum[i][j]+=sum[i][j-1]; int ans=0; for(int i=r;i<=5001;i++) for(int j=r;j<=5001;j++) ans=max(ans,sum[i][j]+sum[i-r][j-r]-sum[i][j-r]-sum[i-r][j]); printf("%d\n",ans); return 0; }