SRM565 Div1 Easy

250

DP[どこまで見た][いくら使った] = 合計

class MonstersValley {
public:
  int minimumPrice(vector<long long> dread, vector <int> price)
  {
    const int N = 50 + 5;
    const int M = N * 2;
    lli dp[N][M];
    const lli inf = 1LL << 60;
    fill(&dp[0][0], &dp[N - 1][M - 1] + 1, -inf);
    dp[0][0] = 0;

    const int n = dread.size();
    const int m = n * 2 + 1;

    for (int nth = 0; nth < n; ++nth) {
      for (int p = 0; p < m; ++p) {
        if (dp[nth][p] < 0) continue;
        const lli& curr = dp[nth][p];
        lli& next = dp[nth + 1][p + price[nth]];
        next = max(next, curr + dread[nth]);
        if (dread[nth] <= curr) dp[nth + 1][p] = max(dp[nth + 1][p], dp[nth][p]);
      }
    }
    for (int p = 0; p < m; ++p) {
      if (0 <= dp[n][p]) return p;
    }
    return 0;
  }
};