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; }