JOI2012本選４番

講義資料 - いもす研 (imos laboratory)
↑参照。
累積和を使ったコード

#include <stdio.h>
int nails[5010][5010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);
		nails[a][b]++,nails[a][b+1]--;
		nails[a+x+1][b]--,nails[a+x+2][b+1]++;
		nails[a+x+1][b+x+2]++,nails[a+x+2][b+x+2]--;
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;j<5010;j++){
			a+=nails[i][j];
			nails[i][j]=a;
		}
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;j<5010;j++){
			a+=nails[j][i];
			nails[j][i]=a;
		}
	}
	for(int i=0;i<5010;i++){
		int a=0;
		for(int j=0;i+j<5010;j++){
			a+=nails[i+j][j];
			nails[i+j][j]=a;
		}
	}
	int ans=0;
	for(int i=0;i<5010;i++)
		for(int j=0;j<5010;j++)
			if(0<nails[i][j])
				ans++;
	printf("%d\n",ans);
	return 0;
}

最大値の伝搬を使ったコード（ただし後ろから）。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int nails[5010][5010];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	memset(nails,0,sizeof(nails));
	for(int i=0;i<m;i++){
		int a,b,x;
		scanf("%d%d%d",&a,&b,&x);
		nails[a+x][b+x]=max(nails[a+x][b+x],x+1);
	}
	int ans=0;
	for(int y=n;0<=y;y--)
		for(int x=n;0<=x;x--){
			if(0<nails[y][x])
				ans++;
			if(0<x)
				nails[y][x-1]=max(nails[y][x-1],nails[y][x]-1);
			if(0<x&&0<y)
				nails[y-1][x-1]=max(nails[y-1][x-1],nails[y][x]-1);
		}
	printf("%d\n",ans);
	return 0;
}