Similar to the official solution, define task \(i\) to be walk from coordinate \(0\) to \(X_i\), push button \(i\), then walk back to coordinate \(0\).

Suppose that tasks are ordered by increasing \(T_i-X_i\). Define “time to spare” \(d_i\) be \(T_i+D-X_i-2\sum_{\text{task }j \text{ is done before task }i} X_j\). Then an order is good iff \(d_i \geq 0\) and \(d_i-d_j \leq D\) when task \(i\) is done before task \(j\). (when \(d_i\) is too large, waiting is needed)

By exchange argument, it can be proven that if \(i>j\) and task \(i\) is done just before task \(j\), we can swap \(i\) and \(j\) if there is a task \(k\neq i,j\) such that \(k<i\) and task \(k\) is done after task \(i\). Therefore if task \(x\) is done last, the sequence must be \((\dots,x+1,x+2,\dots,N,x)\).

So we can do \(dp_{i,j}=\) the minimum possible \(\max(d_{p_1},d_{p_2},\dots,d_{p_i})\) where \(\{p_1,p_2,\dots,p_i\}=\{1,2,\dots,j-1,j+1,\dots,i+1\} \). There are at most \(2\) possible transitions from each state, resulting in \(O(N^2)\) time complexity.