AOJ 2015 - Square Route

Square Route
提出コード
まずは累積和で、上端から、および左端からi番目の道路までの距離を求めておきます(s[i]とします)。
すると、ある道路からある道路までの幅が、累積和の引き算s[i]-s[j]等で求められるので、ありうるすべての取り方を記録します。
縦横それぞれの幅の取り方を昇順でソートします。あとは、どちらか片方を全探索して、その幅と同じものがもう片方にどれだけ存在するか、というのを二分探索で調べれば終わりです。