そう難しい問題ではないはずなのに、ACまでに$1$時間かかった。つらい。

solution

二分探索からのDP。$O(N {(\log N)}^2)$。$O(N \log N)$でもできそう。

対(最大の難しさ,難しさの総和)を最小化する問題。$(d, f(d))$と書いて$d$に関して二分探索すればよい。

$d = \mathrm{limit}$を固定しての$f(d)$の計算を考える。 これはDPで$O(N)$。 いくつ処理したかから難しさの総和への関数$\mathrm{dp} : N+1 \to \mathbb{N \log N}$を \(\mathrm{dp}(i) = \begin{cases} 0 & (i = 0) \\\\ \min \\{ \mathrm{dp}(j) + \sum\_{j \lt k \lt i} d_k \mid t_i - t_j \ge K \land \forall k. j \lt k \lt i \to d_j \le \mathrm{limit} \\} \cup \\{ \mathrm{dp}(j) + \sum\_{j \lt k \le i} d_k \mid \forall k. j \lt k \lt i \to d_j \le \mathrm{limit} \\} & (d_i \le \mathrm{limit}) \\\\ \min \\{ \mathrm{dp}(j) + \sum\_{j \lt k \lt i} d_k \mid t_i - t_j \ge K \land \forall k. j \lt k \lt i \to d_j \le \mathrm{limit} \\} & (d_i \gt \mathrm{limit}) \end{cases}\)とする。($\min$の対象が空になって)これが定義できないならそもそも$\mathrm{limit}$が小さすぎて不可能ということ。 さらに$\mathrm{dp}(n) = \sum^n d_i - \mathrm{dp’}(n)$となるような$\mathrm{dp’}$を考える。 $\mathrm{dp’}$の式では$\sum d_kが消えて単調増加になる(本当か？)ので、親$j$が二分探索で求まる。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
const ll inf = ll(1e18)+9;
int main() {
    // input
    int n, k; cin >> n >> k;
    vector<ll> t(n+1), d(n); {
        t[0] = - k;
        repeat (i,n) cin >> t[i+1] >> d[i];
    }
    // compute
    ll sum_d = whole(accumulate, d, 0ll);
    auto func = [&](ll limit) {
        vector<ll> dp(n+1, - inf); // dp
        dp[0] = 0;
        int last = 0;
        repeat (i,n) {
            int j = (whole(upper_bound, t, t[i+1]-k) - 1) - t.begin();
            assert (t[i+1] - t[j] >= k);
            if (d[i] <= limit) {
                dp[i+1] = dp[i];
                if (last <= j) setmax(dp[i+1], dp[j] + d[i]);
            } else {
                if (j < last) return inf;
                dp[i+1] = dp[j] + d[i];
                last = i+1;
            }
            assert (dp[i+1] <= inf);
        }
        return sum_d - dp[n];
    };
    vector<ll> sorted_d = d;
    sorted_d.push_back(-1);
    sorted_d.push_back(0);
    whole(sort, sorted_d);
    sorted_d.erase(whole(unique, sorted_d), sorted_d.end());
    int l = 0, r = n+1; // (l, r], binary search
    while (l+1 < r) {
        int m = (l + r) / 2;
        (func(sorted_d[m]) < inf ? r : l) = m;
    }
    // output
    ll limit = sorted_d[r];
    cout << limit << endl;
    cout << func(limit) << endl;
    return 0;
}