D - Zabuton

https://atcoder.jp/contests/cf17-final-open/tasks/cf17_final_d

教育的典型

思考

参加者の順番が決まったらdpでできそう。

というかそうでもないと解ける気がしない。

順番を決める時の典型テクで「隣り合う二項間の優先順位が決まればソート出来る」というものがある。（前の人たちを並び替えても後ろに影響が出ないとき使える。）

具体的には

s枚積まれているとき h1 p1 と h2 p2 の優先度を考える

1 2 の順に積むとき  s + p1 <= h2 なら全員積める

1 2 の順に積むとき  s + p2 <= h1 なら全員積める

変形するとそれぞれ s <= h2 - p1 , s <= h1 - p2 となり、　h2 - p1 > h1 - p2なら 1 2 の順に積んだほうがいいと分かる　よってソートできる

後はdp[i][j] := i人目でj人積んでいるときの高さの最小

とすればいい

https://atcoder.jp/contests/cf17-final-open/tasks/cf17_final_d

void solve() {
    cin >> n;
    na2(a, b, n);
    sortp(a, b, [&](P a, P b) { return b.fi - a.se > a.fi - b.se; });
    //i番目にj人つむ最小
    vvi(dp, 5050, 5050, linf);
    dp[0][0] = 0;
    rep(i, n) {
        rep(j, i + 1) {
            if (dp[i][j] >= linf)con;
            //tumu
            if (dp[i][j] <= a[i])chmi(dp[i + 1][j + 1], dp[i][j] + b[i]);
            //tumanu
            chmi(dp[i + 1][j], dp[i][j]);
        }
    }
    rer(i, n) {
        if (dp[n][i] < linf)fin(i);
    }
}