ARC105 C - Camels and Bridge (500)
一番重いラクダが一番小さい耐荷重より重い場合、その橋を絶対に通れないため不可能
コンテスト中は最大小の条件を逆に書いていた
Nが小さいので全ての順列に対してi番目のラクダまで見てj番目までの橋を通ったときの距離を求めたいが、$ O(N! NM)かかるので不可能
それぞれの耐荷重で最も長い橋を記録し、セグ木に載せる
座標圧縮して載せた
全ての順列で以下を試す
全ての2区間でその区間の重さの和未満で最も長い橋の長さを求める
同じ長さなら端を含まないのでOKのはずだがコンテスト中は含んでいたのでWA
前の方からそのラクダがどれだけ前に置けるか求める
$ pos[i] = \max_j (pos[j] + d[j][i]) のようにそれまでのそれぞれの要素の位置と必要な距離の和の最大値が置ける限界の位置になる
全ての順列での$ pos[n-1]の最小値が答え
セグ木の準備が$ O(M \log M)、全ての順列で試すのが$ O(N! N^2 \log M)