以下是来自日本的官方日本新闻原版PDF,已完整保留并按原样染色。


可复制的 PDF 提取文本
Pyramid: 貫きピラミッド
input ファイル“pyramid.in”
output 標準出力
ソースファイルpyramid.c/pyramid.cpp
時間制限5 秒/ データ
古代JOI 王国では,国王の墓として砂漠にピラミッドを作る風習があった.この国では,国
王が死ぬと,占いによって決められる「ある場所」に,占いによって決められる「ある高さ」の
ピラミッドを作ることになっている.
JOI 王国の砂漠は東西幅がW,南北幅がH の長方形の形をしている.砂漠は1 × 1 の正方形
の区画に分かれており,各区画は0 ≦x < W, 0 ≦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 のピラミッ
ドを作った場合,各区画に積まれている石の数は以下のようになる.
1 2 2 2 1 0 0
1 2 3 2 1 0 0
1 2 2 2 1 0 0
1 1 1 1 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
しかし,JOI 王国はそれほど広くはないため,ピラミッドは過去のピラミッドと「重なって」
作られることもある.すなわち,新たにピラミッドを作ろうとしてある区画にn 個の石を積む
ことになった場合に,その区画に既にn 個以上の石が積まれていた場合は,その区画には何も
しない.一方,その区画にまだn 個未満しか石が積まれていなかった場合は,その区画に積ま
れている石の数をn 個まで増やす.
貫きピラミッド–1/2
そのため,多数のピラミッドが作られた末の見た目は複雑となる.たとえば上図の状態で,さ
らに区画(4, 3) を中心とする高さ4 のピラミッドを作ると,各区画に積まれている石の数は以下
のようになる.
1 2 2 2 1 1 1
1 2 3 2 2 2 2
1 2 2 3 3 3 2
1 1 2 3 4 3 2
0 1 2 3 3 3 2
0 1 2 2 2 2 2
さて,考古学者であるあなたは,一体どれほどの数の石がピラミッドの建設に用いられてい
るかを知りたくなった.
全てのピラミッドの中心位置の区画と高さが与えられた時,それらを建設するのに必要な石
の数を求めるプログラムを書け.
Input. 入力ファイルpyramid.in の1 行目は3 つの整数W, H, N (1 ≦W, H ≦3000, 1 ≦
N ≦10 000) が書かれている.W, H はそれぞれ砂漠の横幅,縦幅を表す.また,N はピラミッ
ドの個数を表す.
2 行目以降のi + 1 行目(1 ≦i ≦N) には,3 つの整数xi, yi, hi (0 ≦xi < W, 0 ≦yi < H, 1 ≦
hi ≦3000) が書かれている.これらは,i 番目のピラミッドの中心位置の区画が(xi, yi) であり,
高さがhi であることを表す.
Output. 出力は,標準出力に行うこと.全てのピラミッドを建設するのに必要な石の数を表
す1 つの整数を出力せよ.
採点基準採点用データのうち,配点の10% 分については,W, H ≦1000, N ≦5 を満たす.ま
た,配点の25%分については,W, H ≦500 かつ,全てのピラミッドの高さが100 以下である.
例1
pyramid.in 標準出力
7 6 2 81
2 1 3
4 3 4
例2
pyramid.in 標準出力
3000 3000 1 17999999500
1500 1500 3000
貫きピラミッド–2/2