drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ JOI JOI春合宿 JOI難易度5 AtCoder 累積和 二次元累積和 【問題集】累積和 【問題集】二次元累積和 累積和テク:区間の総和を累積和で高速に求める NoviSteps2Q 二次元累積和！！ ジャッジページ 問題文 問題概要 のグリッドが与えられる。各マスには整数値 が描かれている。整数値は 以上 以下である。 これらのグリッド中の の長方形領域であって、その内部に -1 を含まないものを考える。そのような長方形領域に含まれる値の総和の最小値を求めよ。 ただし、内部に -1 を含まない長方形領域が存在することは保証される。 制約 考えたこと 整数値 -1 を INF に置き換えておけば、任意の長方形領域を考える問題に置き換えることができる。 このとき、 の二次元累積和を求めておけば、各長方形領域の値の総和はそれぞれ で求めることができる。二次元累積和について、詳細… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F12%2F22%2F155000" title="JOI 春合宿 2007 day1-3 Mall (2Q, 難易度 5) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-12-22 15:50:00 rich https://drken1215.hatenablog.com/entry/2020/12/22/155000 1.0 100%