hotpepsiの練習帳

SRM 636

15:03

Div1 Easy (250)

問題

• チョコレートを9分割する
• それぞれの部分の合計値がその部分の品質になる
• もっとも品質が低い部分の最高値を求める

方針

• 分割する位置は縦2つ、横2つなので全探索する
• 全部再計算すると重そうなので、(0,0)から全ての点(x,y)の合計を求めておく
• (a,b)から(c,d)の合計は、(c,d)の合計から、(a-1,d),(c,b-1)の合計を引いて(a-1,b-1)の合計を足すので、表で作っておく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_636/ChocolateDividingEasy.cpp

結果

o-- 104.40pts 413rd/532 rating 1649 -> 1564 (-85)

やややるだけゲー。遅い

http://togetter.com/li/731920