Submission

Score: 100

User: kittipos

Problemset: laracroft

Language: cpp

Time: 0.087 second

Submitted On: 2026-03-05 20:44:56

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

vector<int> value;
vector<int> weight;

vector<vector<vector<int>>> dp; //i, m, p

int solve(int i, int m, bool p) {
  if (m < 0) {
    return numeric_limits<int>::min();
  }
  if (m == 0 || i < 0) {
    return 0;
  }
  if (dp[i][m][p] != -1) {
    return dp[i][m][p];
  }

  int res = solve(i-1, m, true);
  if (p) {
    res = max(res, solve(i, m-weight[i], false) + value[i]);
  }
  dp[i][m][p] = res;

  return res;
}

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

  int n, m;
  cin >> n >> m;
  value.resize(n);
  weight.resize(n);
  dp.assign(n, vector<vector<int>>(m+1, vector<int>(2, -1)));

  for (int i = 0; i < n; i++) {
    cin >> value[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> weight[i];
  }

  int best_value = solve(n-1, m, true);
  for (int i = 0; i <= m; i++) {
    if (solve(n-1, i, true) == best_value) {
      cout << best_value << ' ' << i;
      return 0;
    }
  }

  return 0;
}