ABC250 F - One Fourth (500)
コンテスト中の考察
それぞれの点から$ \frac{S}{4}に近い点を二分探索で左右で求める
全面積を計算時から8倍しておくと楽
WA
WAにならなくても二分探索を使っても結局各点までの面積を全て求める必要があるので$ \mathcal{O}(N^2)以上でTLEになる
解説の解法
尺取法で行う
どんどんと右端の点を動かして面積を増やし、目標を超えたら左端の点を動かす
点を動かして面積を再計算する度に最小値を更新
1周だと端の処理が甘かったらしく2周にしたらAC