問題の言い換え
ダメージの累計が最小になる様に手裏剣を使う．
思考の流れ
いくつか思いつくことがある．
- まず暫定的な答えを出す．これは簡単に求まるというのが大事． 手裏剣を 0枚使ったときの求めて，その答えを修正していく． 手裏剣 1枚でどれくらい得をするのかを考える．
- 敵が 1体のときに，\(x = 0, 1\) で場合分けして考える．
- 敵が \(N\) 体で，全て \(x = 0\) の場合を考える． \(x = 1\) の場合は，手裏剣を投げることで \(x=0\) に帰着できるから．
それぞれについて詳しく見ていく．
敵が 1体のとする．手裏剣を \(u\) 枚使ったとする．
- \(x = 0\) なら \(b-u-1\) 回攻撃を食らう． これは \(u=0\), \(u > 0\) による場合分けは不要．
- \(x = 1\) なら，手裏剣を投げるかどうかで場合分け．
- \(u = 0\) のときは，\(b - u\) 回攻撃をくらう．
- \(u > 0\) のとき
- \(b > 1\) のとき，先手をとれるおかげで \(b-u-1\) 回攻撃をくらう．
- \(b = 1\) のとき，0回攻撃を食らう．
まとめると， \(x = 1\)のときは基本的に手裏剣 1枚目だけダメージが \(2a\) 得するが， \(b = 1\) のときは \(a\) 得する． \(1\) 枚投げれば，\(x = 0\) に帰着できる． \(x = 0\)のときは，1枚につき \(a\) 得する．
また，手裏剣を 0枚使ったときの暫定的な答えはすぐに求まる．
注意
\(x = 1\) かつ \(b = 1\) のときは，手裏剣を \(1\)枚投げても \(a\) しか得をしない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
using T = tuple<ll,ll,ll,ll>;
priority_queue<T> ts;
rep(i,n){
ll a,b,x; cin >> a >> b >> x;
ll c = (x+1) * a;
if(b == 1) c = a; // b == 1 && x == 1
ts.push({c, a, b, x});
dmg += (b-(!x))*a; // 手裏剣を使わなかったときのダメージ
}
// 手裏剣を上手に配分してダメージを減らす
while(ts.size() && m > 0){
auto [c, a, b, x] = ts.top(); ts.pop();
if(x == 1){
dmg -= c;
m--;
b--;
if(b > 0) ts.push({a,a,b,0}); // x = 1 は 1枚目の手裏剣だけ特別．2枚目以降は x = 0 に帰着．
}else{
ll use = min(m, b-1);
m -= use;
dmg -= use * a; // 手裏剣を使ってどれだけ得するか
}
}
cout << dmg << endl;
return 0;
}
