7K12 blog

猫でも分かるアルゴリズム解説

GigaCode 2019 D - 家の建設

f:id:tkr987:20200516005245p:plain

https://atcoder.jp/contests/gigacode-2019/submissions/13237369

  • 長方形の全組み合わせは O(H^2 W^2)

f:id:tkr987:20200516005605p:plain

長方形の全ての組み合わせについてT=土地の値段合計+面積×Kを計算し、Tが所持金V以下になる長方形のうち最大の面積が答えになる。長方形は座標P1からP4の組み合わせで表現できるため、長方形を選ぶ組み合わせ計算量は O(H^2 W^2)になる。土地の値段合計は二次元累積和を使うと O(1)になるのでTLEせず間に合う。