#1158182 (C++23) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: Enderaoe Lyther
• 提出日時: 2026-04-17 22:20:32
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 4,795 bytes
• コンパイル時間: 2,215 ms
• コンパイル使用メモリ: 176,292 KB
• 実行使用メモリ: 284,368 KB
• 最終ジャッジ日時: 2026-04-17 22:21:34
• 合計ジャッジ時間: 15,575 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	-- * 1
other	RE * 30 TLE * 1 -- * 29

ソースコード

#include <algorithm>
#include <iostream>
#include <vector>

using int64 = long long;
using i128 = __int128_t;

static constexpr i128 NEG = (i128)1 << 120;

static void print_i128(i128 x) {
  if (x == 0) {
    std::cout << "0\n";
    return;
  }
  if (x < 0) {
    std::cout << '-';
    x = -x;
  }
  std::string s;
  while (x > 0) {
    s.push_back(char('0' + int(x % 10)));
    x /= 10;
  }
  std::reverse(s.begin(), s.end());
  std::cout << s << '\n';
}

static inline bool feas_j_jp(int64 j, int64 jp, int B, int D) {
  int64 b_lo = std::max<int64>(0, jp - j);
  int64 b_hi = std::min<int64>(B, jp - j + D);
  return b_lo <= b_hi;
}

static inline i128 day_val(const std::vector<i128> &dp, int64 j, int64 jp,
                           int A, int B, int C, int D) {
  if (j < 0 || j >= (int64)dp.size() || dp[(size_t)j] <= NEG / 4) {
    return NEG;
  }
  int64 b_lo = std::max<int64>(0, jp - j);
  int64 b_hi = std::min<int64>(B, jp - j + D);
  int coeff = C - A;
  int64 b = (coeff > 0) ? b_hi : (coeff < 0 ? b_lo : b_lo);
  int64 d = j + b - jp;
  return dp[(size_t)j] - (i128)b * A + (i128)d * C;
}

static void relax_K(std::vector<i128> &ndp, int64 K, int A, int B, int C, int D,
                    int64 j, i128 g) {
  if (g <= NEG / 4) {
    return;
  }
  int coeff = C - A;
  int64 L1 = std::max<int64>(0, K - j);
  int64 R1 = std::min<int64>(B, K - j + D);
  if (L1 <= R1) {
    int64 b = (coeff > 0) ? R1 : (coeff < 0 ? L1 : L1);
    int64 d = j + b - K;
    i128 ng = g - (i128)b * A + (i128)d * C;
    ndp[(size_t)K] = std::max(ndp[(size_t)K], ng);
  }
  int64 L2 = K - j + D + 1;
  if (L2 <= B && j + L2 >= K) {
    int64 b = L2;
    i128 ng = g - (i128)b * A + (i128)D * C;
    ndp[(size_t)K] = std::max(ndp[(size_t)K], ng);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int T;
  std::cin >> T;
  const i128 start = 10100;
  while (T--) {
    int N;
    int64 K;
    std::cin >> N >> K;
    std::vector<int> A(N), B(N), C(N), D(N);
    int64 sumB = 0;
    for (int i = 0; i < N; ++i) {
      std::cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
      std::cin >> B[i];
      sumB += B[i];
    }
    for (int i = 0; i < N; ++i) {
      std::cin >> C[i];
    }
    for (int i = 0; i < N; ++i) {
      std::cin >> D[i];
    }

    int64 Wcap = std::min<int64>(K, sumB);
    int64 W = 0;
    std::vector<i128> dp((size_t)Wcap + 1, NEG);
    dp[0] = start;

    for (int di = 0; di < N; ++di) {
      int a = A[di], b = B[di], c = C[di], d = D[di];
      int64 W2 = std::min<int64>(K, W + b);
      std::vector<i128> ndp((size_t)W2 + 1, NEG);

      if (K == 0) {
        i128 best = NEG;
        for (int64 j = 0; j <= W; ++j) {
          if (dp[(size_t)j] <= NEG / 4) {
            continue;
          }
          for (int bb = 0; bb <= b; ++bb) {
            for (int dd = 0; dd <= d; ++dd) {
              if (dd > j + bb) {
                continue;
              }
              if (j + bb - dd != 0) {
                continue;
              }
              i128 ng = dp[(size_t)j] - (i128)bb * a + (i128)dd * c;
              best = std::max(best, ng);
            }
          }
        }
        ndp[0] = best;
      } else {
        int64 lim = std::min<int64>(K - 1, W + b);
        bool full = true;
        for (int64 j = 0; j <= W; ++j) {
          if (dp[(size_t)j] <= NEG / 4) {
            full = false;
            break;
          }
        }
        if (full) {
          int64 opt = 0;
          for (int64 jp = 0; jp <= lim; ++jp) {
            while (opt <= W &&
                   (!feas_j_jp(opt, jp, b, d) || dp[(size_t)opt] <= NEG / 4)) {
              ++opt;
            }
            if (opt > W) {
              continue;
            }
            while (opt + 1 <= W && feas_j_jp(opt + 1, jp, b, d) &&
                   day_val(dp, opt + 1, jp, a, b, c, d) >=
                       day_val(dp, opt, jp, a, b, c, d)) {
              ++opt;
            }
            ndp[(size_t)jp] =
                std::max(ndp[(size_t)jp], day_val(dp, opt, jp, a, b, c, d));
          }
        } else {
          for (int64 jp = 0; jp <= lim; ++jp) {
            i128 best = NEG;
            int64 j0 = std::max<int64>(0, jp - d);
            int64 j1 = std::min<int64>(W, jp + b);
            for (int64 j = j0; j <= j1; ++j) {
              best = std::max(best, day_val(dp, j, jp, a, b, c, d));
            }
            ndp[(size_t)jp] = best;
          }
        }

        if (W2 == K) {
          for (int64 j = 0; j <= W; ++j) {
            relax_K(ndp, K, a, b, c, d, j, dp[(size_t)j]);
          }
        }
      }

      dp.swap(ndp);
      W = W2;
    }

    i128 ans = NEG;
    for (int64 j = 0; j <= W; ++j) {
      ans = std::max(ans, dp[(size_t)j]);
    }
    print_i128(ans - start);
  }
  return 0;
}