SRM660 div1 250

むずい

問題

n*mのセルに0〜9の数字が書かれている。
あるセル(i,j)を選んだ時、p個の(i+x[k],j+y[k])に書かれている数字をすべて抽出し、その合計を得られる。(範囲外は0を抽出)
今、ある2つの異なるセルを選び、同じセルから1回のみ抽出できる場合、合計値の最大値を求めよ。

2<=n,m<=100
-(n-1)<=x[k]<=(n-1)
-(m-1)<=y[k]<=(m-1)
1<=p<=10

考え方

愚直な方法だと、2つのセルを選んで、2*p個を確認し、最大値を求めるので、計算回数は100*100*100*100*20=2*10^9回程度になってしまう。
そこで、1つのセルを固定した状態で、合計値が最大となるもう一つのセルを高速に求める方法を考える。

まず、セルを選んで無い状態で、すべてのセルについて、そのセルを選んだ時に得られる合計値と座標を降順に求めておく。
これを使って、1つ目のセルを固定した後、もう一つのセルを選ぶときは合計値が大きいものから見て、「かぶりを無視した2つのセルの合計値」がそれまでの最大値より小さくなったら打ち切り、とするのが考えられる。
しかし、すべてのセルが同じ合計値の場合は、100*100個すべて見る可能性があり、TLE。

さらに考察すると、1つ目と2つ目のセルの抽出セルがかぶらないならば単純にそれぞれのセルの合計値を足すだけでよく、それ以降はその合計値以下しかないので、そこで打ち切れる、ということがわかる。
そこで、抽出セルがかぶらないようなセルが何個目ぐらいにでてくるかを考える。
1つ目のセルのk1個目の抽出セルが2つ目のセルのk2個目の抽出セルとかぶってると考えると、この組み合わせ(k1,k2)は最大でも10*10=100個程度しかありえない。

なので、2つのセルを選んで抽出セルがかぶらないようなセルの選び方は100個程度で見つけられるので、かぶらないようなセルが出てきた時点で打ち切ってよい。
これならば100*100*100*20=2*10^7回で求められる。