Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

AOJ 2364: Lucky Dip

方針

2<=W,H<=1000なので1回到達可能かBFSするのに10^6、
0<=N<=1000なのでNについて線形探索して10^3

  • >10^9で8秒なら間に合うかもしれない…?

しかし、Nがある値以上ならば必ず到達でき、それより小さければ到達できないので
二分探索をすることができる。

  • >O(WHlogN)で充分間に合う。