AOJ 0574 釘

解説みた。
最大値の伝搬を使った

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 5000;
const int MAX_M = 500000;
int N, M;
short nail[MAX_N][MAX_N];
int main(){
	scanf("%d %d", &N, &M);
	for(int i = 0; i < M; i++){
		int a, b, x;
		scanf("%d %d %d", &a, &b, &x);
		a--; b--;
		nail[a][b] = x + 1;
	}
	int ans = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j <= i; j++){
			if(i == 0 && j == 0){ ;
			}else if(j == 0)
				nail[i][j] = (short)max((int)nail[i][j], nail[i-1][j] - 1);
			else
				nail[i][j] = (short)max((int)nail[i][j], max(nail[i-1][j], nail[i-1][j-1]) - 1);
			//printf("%d ", nail[i][j]);
			if(nail[i][j] != 0){
				ans++;
			}
		}
		//puts("");
	}
	printf("%d\n", ans);
	return 0;
}