問題概要
整数 $N$，$M$ と列$L$，$R$，$S$ が与えられる． $M$個の制約 $$\sum\{ A_j \mid j = L_i, \dots, R_i \} = S_i$$ を満たす長さ $N$ の正の整数の列 $A$ が存在するかどうか判定し， 存在する場合には $A$ の総和の最小値を求めよ．
制約
$1 \leq N, M \leq 4000$，$1 \leq S_i \leq 10^9$
解
略解．click to open
牛ゲー．累積和 $B_i := \sum\{A_j \mid 0 \leq j < i\}$ に関して，次を解けば良い．
- 次の条件の下で，$B_{N + 1} - B_{1}$ を最小化する
- $B_{i + 1} - B_i \geq 1$
- $B_{R_{i} + 1} - B_{L_i} \geq S_i$
- $B_{R_{i} + 1} - B_{L_i} \leq S_i$