ABC155 D - Pairs (400)
考察
全通りを実際に試すのはTLEする
K番目に来る値を決め打ちすれば二分探索で正しいか判定できる
コンテスト中は正負で混乱したり仕様を勘違いしたりして駄目
Kの値を二分探索する
その値以下で達成できるかはその値以下の積をK個作れるかで判定
それぞれの$ a_iに対して配列のどの部分からどの部分までで積がK以下になるか二分探索
$ a_iの正負によってok, ngの条件が逆になる
$ a_i = 0だけ特別に場合分けを更にした
一回の二分探索内での判定が$ O(N\log N)
二分探索の回数が$ O(\log N)
全体で$ O(N (\log N)^2)