← 返回题目列表

AtCoder · joisc2007_mall

mall. 购物中心(Mall)

中文机器翻译题面 查看原题

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

ショッピングモール (Mall) - 原题 PDF 第 1 页
原题PDF第3页
ショッピングモール (Mall) - 原题 PDF 第 2 页
原题PDF第4页
可复制的 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