JOI O(N) Contest

JOIのコンテストなのでぬるいのが1問くらいあると思ったら全然そんなことなかった

A

入力を読みながらスタックに乗せていき、∧な形ができたら登るか掘るかの短いほうの時間におきかえていく。これでO(N)で解ける
速さ1でばかりテストしていたせいでバグがなかなか取れなかったorz

B

M+1権利を使わない場合の飛んでいく順はBITなりなんなりでO(NlogN)で求まる
あとは後ろから適当に見ていけばよい
後半部をO(N^2)にして50点取れていたが終了間際にO(NlogN)のを出したらところどころWAで死亡orz

C

凸包が4点以上なら最適は凸らしい。Rotating Calipersで求まる
O(N^3)くらいのものを投げておいた

result

100 + 20 + 30 = 150
2位

負けたorz