GigaCode2019 D - 家の建設 (100)
事前に累積和を求めておく
単純に全組み合わせを試すと
$ O(H^2W^2)
でTLEしそう
実際は通るらしい
左上と縦の長さを決める
横の長さは二分探索で求める
横に伸ばした時に、土地の価格とKの分だけ費用は単調増加する
$ O(H^2W \log W)
で間に合う
問題:
https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_d
提出:
https://atcoder.jp/contests/gigacode-2019/submissions/8596770
#GigaCode2019
#D