Submission

Score: 100

User: Quaoar

Problemset: laracroft

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-04 21:04:49

#include <bits/stdc++.h>
using namespace std;
int dp[501][2001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , W;
    cin >> n >> W;
    vector <int> price(n);
    vector <int> weight(n);
    vector <int> select;
    for (int i = 0 ; i < n ; i++) cin >> price[i];
    for (int i = 0 ; i < n ; i++) cin >> weight[i];

    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= W ; j++){
            if (j >= weight[i - 1]){
                dp[i][j] = max(dp[i-1][j - weight[i-1]] + price[i-1] , dp[i-1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            } 
        }
    }

    /*
    for (int i = 0 ; i <= n ; i++){
        for (int j = 0 ; j <= W ; j++){
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    */
    int min_weight;
    for (int i = W ; i > 0 ; i--){
        if (dp[n][W] == dp[n][i]){
            min_weight = i;
        }
    }


    if (dp[n][W] == 0){
        cout << 0 << " " << 0;
        return 0;
    }
    cout << dp[n][W] << " "  << min_weight;
    return 0;
}