Submission #66787154

---

Source Code Expand

// 綺麗に解きなおし

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, h, m;
  cin >> n >> h >> m;

  vector<int> a(n), b(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i) >> b.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  //////////////////// 処理 ////////////////////

  // 動的計画法用の二次元vector
  // dp.at(i).at(j)は、i体のモンスターを倒すのに、体力がjあったら魔力はいくつ必要か
  vector<vector<int>> dp(n+1,vector<int>(h+1,0));

  // i体目までモンスターを倒している状態で次がどうなるか
  for (int i=0; i<n; i++) {

    // 体力がjである場合にどうなるか
    for (int j=0; j<=h; j++) {

      // 次のモンスターを体力消費で倒す場合
      int next1;
      if (j>=a.at(i)) next1 = dp.at(i).at(j-a.at(i));
      else next1 = 1e9;

      // 次のモンスターを魔力消費で倒す場合
      int next2 = dp.at(i).at(j) + b.at(i);

      // 2つのうち小さい方がそこの値
      dp.at(i+1).at(j) = min(next1,next2);

    }

  }

  // 魔力m以下で倒せる限界数を探す
  for (int i=n; i>=0; i--) {
    if (dp.at(i).back()<=m) {
      result = i;
      break;
    }
  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result