Submission

Score: 100

User: goine

Problemset: laracroft

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-22 08:20:55

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

int main() {
    int item_count, capacity;
    cin >> item_count >> capacity;

    vector<int> values(item_count + 1);
    vector<int> weights(item_count + 1);
    for (int i = 1; i <= item_count; i++) {
        cin >> values[i];
    }

    for (int i = 1; i <= item_count; i++) {
        cin >> weights[i];
    }

    vector<vector<int>> dp(item_count + 1, vector<int>(capacity + 1));
    for (int item_index = 1; item_index <= item_count; item_index++) {
        for (int weight = 0; weight <= capacity; weight++) {
            dp[item_index][weight] = dp[item_index - 1][weight];

            if (weight >= weights[item_index]) {
                dp[item_index][weight] = max(
                    dp[item_index][weight],
                    dp[item_index - 1][weight - weights[item_index]] + values[item_index]
                );
            }
        }
    }

    int answer = capacity;
    for (int i = capacity - 1; i >= 0; i--) {
        if (dp[item_count][i] < dp[item_count][capacity]) {
            break;
        }
        answer = i;
    }

    cout << dp[item_count][capacity] << ' ' << answer;
    return 0;
}