計算量を見ると，\(O(N * sum(Z))\) は間に合う． ここから DP を考えるというよりは，まずは自然に考える． 簡単に思いつくのは，\(i\) を固定したときの様子を探ること．
\(i \in N\) を固定したとき何人を鞍替えさせれば良いかを考える． 鞍替えさせる人数を \(d \in \mathbb{N}\) 人とする．
- \(y_{i} < x_{i}\) のときは\(d = 0\)
- \(y_{i} > x_{i}\) のときは \(y_{i} - d < x_{i} + d \) を満たせばよい． よって，\(d > (y_{i} - x_{i})/2\) が必要十分． 一番小さい取り方は，\(d = \lfloor (y_{i}-x_{i})/2 \rfloor + 1\).
つまり， \(i\) を固定すれば，何人鞍替えすれば良いかは一意に定まる．
これを踏まえると，次の DP が作れる．
\(dp_{i,s} := [0,i)\) まで調べて，議席 \(s\) を獲得するための最小の鞍替え人数.
これは部分和 DP の様に可能．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll x(n), y(n), z(n);
rep(i,n){
cin >> x[i] >> y[i] >> z[i];
}
ll tot = 0;
rep(i,n){
tot += z[i];
}
vll dp(tot+1, INFL);
dp[0] = 0;
rep(i,n) {
drep(s, tot+1){
ll t = s + z[i];
ll d = 0;
if(y[i] > x[i]){
d = (y[i]-x[i])/2 + 1;
}
if(t <= tot) chmin(dp[t], dp[s] + d);
}
}
ll ans = INFL;
srep(t, ceil(tot,2LL), tot+1){
chmin(ans, dp[t]);
}
cout << ans << endl;
return 0;
}
