JOI春合宿 2009-day1 pyramid

問題文 : 貫きピラミッド

解法 :
自分の地点での大きさを, 次のように, 2方向から伝搬しながら更新してやれば良い.どちらから先に行なっても良い.

この更新が終われば, あとは各マスの和を取るだけである.

O(WH)回の上書きで答えが求まるので, 計算量はO(WH)時間となる. ただし, 2方向 * 4つの隣接するマス で生じる定数 8 に注意.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long lint;

int dx[2][4] = {{-1, -1, 0, 1}, {1, 1, 0, -1}};
int dy[2][4] = {{0, -1, -1, -1}, {0, 1, 1, 1}};

int w, h, n;

int map[3000][3000];

bool ok(int y, int x)
{
	return (0 <= y && y < h && 0 <= x && x < w);
}

int main()
{
	scanf("%d %d %d", &w, &h, &n);
	
	for (int i = 0; i < n; i++){
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		map[y][x] = max(map[y][x], z);
	}
	
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			for (int k = 0; k < 4; k++){
				int ny = i + dy[0][k], nx = j + dx[0][k];
				if (ok(ny, nx)) map[i][j] = max(map[i][j], map[ny][nx] - 1);
			}
		}
	}
	
	for (int i = h - 1; i >= 0; i--){
		for (int j = w - 1; j >= 0; j--){
			for (int k = 0; k < 4; k++){
				int ny = i + dy[1][k], nx = j + dx[1][k];
				if (ok(ny, nx)) map[i][j] = max(map[i][j], map[ny][nx] - 1);
			}
		}
	}
	
	lint ret = 0;
	
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			ret += map[i][j];
		}
	}
	
	printf("%lld\n", ret);
	
	return (0);
}