http://agc016.contest.atcoder.jp/tasks/agc016_c
考察
サンプルケースから考えてみる。
入力 3 3 2 2 出力 Yes 1 1 1 1 -4 1 1 1 1
このサンプルケースのように1を敷き詰めて、最小限-W*Hを入れていく方針で実装すると、一部落ちる。
1を敷き詰めるのではなく、10を敷き詰めて、最小限マイナスを入れてみると以下のようになる。
10 10 10 10 -31 10 10 10 10
こうすると、総和が4から49に増える。
こうすることでよりよい答えが得られる。
解法
http://agc016.contest.atcoder.jp/submissions/1364015
全てにINFを敷き詰めて、最小限-(W*H-1)*INF-1を入れていく。
INFは提出解法では1000にしているが、4000辺りがACを取れる最大である
他のプロは各区間の左上に正の数、右下に負の数を置いてやっていた。
本質的には上の解法と同じである。
