問題 提出コード 解法 番目の数字、が採用される区間について調べてみます。 となる区間について、がその区間の最小値になるには、かつとなる任意のについて、が成り立たなければなりません。 こうなるようなの候補の最小値、の最大値を求めてみます。 これ…

問題 提出コード 解法 毎回愚直に計算するともちろん間に合わないので何か工夫をする必要があります。そこで登場するのが累積和です。 まず、始点と終点も観光スポットとみなし、としておきます。 観光スポットからまで順番に行ったときにかかる金額の総和 …

問題 提出コード 解法 2次元のままこの問題を考えると、いろいろと大変なことになるので、どちらか片方の条件を無視してよくなるような条件を探します。 すると、赤の点と青の点を同時にの昇順、の昇順の優先度でソートを行うと、番目の赤い点と、番目の青い…