Submission

Score: 0

User: Quaoar

Problemset: laracroft

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-03 15:22:47

#include <iostream>
#include <algorithm>
using namespace std;
int n , w;
int value[500];
int weight[500];
int dp[500][500];

int ks(int w , int n){
    if (w == 0 || n == 0){
        return 0;
    }
    if (dp[w][n] != -1){
        return dp[w][n];
    }
    if (weight[n - 1] <= w){
        dp[w][n] = max(ks(w - weight[n - 1] , n - 1) + value[n - 1] , ks(w , n - 1));
        return dp[w][n];
    } else {
        dp[w][n] = ks(w , n - 1);
        return dp[w][n];
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> w;
    bool smth = false;
    for (int i = 0 ; i < n ; i++){
        cin >> value[i];
    }
    for (int i = 0 ; i < n ; i++){
        cin >> weight[i];
        if (weight[i] <= w){
            smth = true;
        }
    }
    if (!smth){
        cout << "0 0";
        return 0;
    }
    for (int i = 0 ; i <= w ; i++){
        for (int j = 0 ; j <= n ; j++){
            dp[i][j] = -1;
        }
    }
    cout << ks(w , n) << " ";

    int sum = 0;
    int currW = w;
    int currN = n;
    
    while (currN > 0 && currW > 0) {
        ks(currW, currN - 1);

        if (dp[currW][currN] != dp[currW][currN - 1]) {
            sum += weight[currN - 1];
            currW -= weight[currN - 1];
        }

        currN--;
    }
    cout << sum ;
    return 0;
}