pyramid - 貫きピラミッド (Pyramid) Editorial /

Time Limit: 5 sec / Memory Limit: 64 MiB

AtCoder での提出方法

標準入力から入力を読み込み,標準出力へ出力すること.

配点 : 100 点

問題文

古代 JOI 王国では,国王の墓として砂漠にピラミッドを作る風習があった.この国では,国王が死ぬと,占いによって決められる「ある場所」に,占いによって決められる「ある高さ」のピラミッドを作ることになっている.

JOI 王国の砂漠は東西幅が W,南北幅が H の長方形の形をしている.砂漠は 1 \times 1 の正方形の区画に分かれており,各区画は 0 \leqq x < W,0 \leqq y < H を満たす整数 x, y によって (x, y) と表現される.区画 (0, 0) は北西隅の区画であり,区画 (x, y) は,区画 (0, 0) から東に x,南に y 進んだ地点に位置する区画である.

さて,ピラミッドは次のようにして作られる.まず,占いによってピラミッドの中心の区画 (X, Y ) と高さ h が決められる.それに従って,次の規則で砂漠内の各区画に石を積むことによってピラミッドを建設する:

  • 区画 (X, Y ) を中心とする高さ h のピラミッドを作る場合,砂漠内の区画 (x, y) には \max\{0,h - \max\{|X - x|,|Y - y|\}\} 個の石を積む.砂漠の外には石は一切積まない.

たとえば,砂漠の大きさが W = 7,H = 6 であり,区画 (2, 1) を中心とする高さ 3 のピラミッドを作った場合,各区画に積まれている石の数は以下のようになる.

2009-pyramid-first.png

しかし,JOI 王国はそれほど広くはないため,ピラミッドは過去のピラミッドと「重なって」作られることもある.すなわち,新たにピラミッドを作ろうとしてある区画に n 個の石を積むことになった場合に,その区画に既に n 個以上の石が積まれていた場合は,その区画には何もしない.一方,その区画にまだ n 個未満しか石が積まれていなかった場合は,その区画に積まれている石の数を n 個まで増やす.

そのため,多数のピラミッドが作られた末の見た目は複雑となる.たとえば上図の状態で,さらに区画 (4, 3) を中心とする高さ 4 のピラミッドを作ると,各区画に積まれている石の数は以下のようになる.

2009-pyramid-second.png

さて,考古学者であるあなたは,一体どれほどの数の石がピラミッドの建設に用いられているかを知りたくなった.

全てのピラミッドの中心位置の区画と高さが与えられた時,それらを建設するのに必要な石の数を求めるプログラムを書け.

入力

入力ファイル pyramid.in の 1 行目は 3 つの整数 W, H, N (1 \leqq W, H \leqq 3000, 1 \leqq N \leqq 10\,000) が書かれている.W, H はそれぞれ砂漠の横幅,縦幅を表す.また,N はピラミッドの個数を表す.

2 行目以降の i + 1 行目 (1 \leqq i \leqq N) には,3 つの整数 x_{i}, y_{i}, h_{i} (0 \leqq x_{i} < W,0 \leqq y_{i} < H,1 \leqq h_{i} \leqq 3000) が書かれている.これらは,i 番目のピラミッドの中心位置の区画が (x_{i}, y_{i}) であり,高さが h_{i} であることを表す.

出力

出力は,標準出力に行うこと.全てのピラミッドを建設するのに必要な石の数を表す 1 つの整数を出力せよ.

採点基準

採点用データのうち,配点の 10\% 分については,W, H \leqq 1000, N \leqq 5 を満たす.また,配点の 25\% 分については,W, H \leqq 500 かつ,全てのピラミッドの高さが 100 以下である.

入力例 1

7 6 2
2 1 3
4 3 4

出力例 1

81

入力例 2

3000 3000 1
1500 1500 3000

出力例 2

17999999500

Source Name

JOI 2008-2009 春季トレーニング合宿 Contest Day1