以下是来自日本的原始新闻PDF,已完整保存并染色。


可复制的 PDF 提取文本
Mall: ショッピングモール
input ファイル“mall.in”
output 標準出力
ソースファイルmall.c/mall.cpp/Mall.java
時間制限6 秒/ データ
クロアチアの首都ザグレブでは,IOI2007 の開催にあわせて,郊外に大型のショッピングモー
ルを建設することにした.ショッピングモールの建設候補地は,下図のように横m ブロック,縦
n ブロックの格子状に区切られている.
建設候補地の例(m = 10, n = 7)
ザグレブ市では,建設候補地の中から横a ブロック,縦b ブロックの長方形の領域を選び,そ
こにショッピングモールを建設することにした.しかし,建設候補地内のいくつかのブロックに
は,すでに人が住んでおり,その土地にはショッピングモールを建設することができない.もし,
横a ブロック,縦b ブロックの長方形領域の中に人が住んでいるブロックが無ければ,その長方
形領域内のブロックを全て買収することにより,ショッピングモールを建設することができる.
ザグレブ市の財政上の理由から,用地買収にかかる費用はできるだけ少なくする必要がある.
予算案を策定するため,ショッピングモール建設のための用地買収に必要な費用を早急に計算
する必要がある.そこで,ザグレブ市では,そのためのプログラムの作成を,IOI2007 の代表
候補者であるあなたに依頼することにした.
入力として,建設候補地の大きさと,ショッピングモールの大きさが与えられ,また,各ブ
ロックごとに,そこに人が住んでいるかどうかの情報と,もし人が住んでいなければそのブロッ
クを買収するのに必要な費用が与えられたとき,ショッピングモール建設のための用地買収に
必要な費用の最小値を求めるプログラムを作れ.
以下では,建設候補地の左からi 列目,上からj 行目のブロックを(i, j) で表す.
Input. 入力ファイルmall.in の1 行目には,2 つの整数m, n (1 ≦m, n ≦1000) が空白を区
切りとして書かれている.これは,建設候補地の大きさが横m ブロック,縦n ブロックである
ことを表す.
ショッピングモール–1/2
2 行目には,2 つの整数a, b (1 ≦a, b ≦1000) が空白を区切りとして書かれている.これは,
ショッピングモールの大きさが横a ブロック,縦b ブロックであることを表す.
続くn 行(3 行目~n + 2 行目) には,建設候補地内の各ブロックの情報が書かれている.j + 2
行目(1 ≦j ≦n) は上からj 行目のブロックの情報を表しており,m 個の整数c1,j, . . . , cm,j
(−1 ≦ci,j ≦100) が空白を区切りとして書かれている.ci,j = −1 のときは,ブロック(i, j) に
人が住んでいることを表す.そうでないときは,ブロック(i, j) の買収にかかる費用がci,j であ
ることを表す.
なお,採点に用いる入力データに対しては,ショッピングモールの建設は常に可能である.
Output. 出力は,標準出力に行うこと.ショッピングモール建設のための用地買収に必要な費
用の最小値を出力せよ.
例
mall.in 標準出力
7 6 184
3 2
26 29 84 15 -1 1 71
45 14 38 91 62 77 35
68 -1 -1 90 63 56 70
31 2 4 74 72 41 90
100 26 21 -1 44 72 60
71 4 40 93 48 -1 50
この入出力例におけるショッピングモール建設地を図示すると,以下の通りである.×のブ
ロックは,すでに人が住んでいることを意味する.
26 29 84 15 × 1 71
45 14 38 91 62 77 35
68 × × 90 63 56 70
31 2 4 74 72 41 90
100 26 21 × 44 72 60
71 4 40 93 48 × 50
注意入力データの大きさに注意すること.特に,C++ のiostream は遅いので,必要に応じ
てfscanf 等を用いるとよいだろう.
ショッピングモール–2/2