Submission

Score: 0

User: Quaoar

Problemset: laracroft

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-04 20:52:46

#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];
            } 
        }
    }
    int i = n;
    int j = W;
    while(i > 0){
        if (j >= weight[i - 1] && dp[i][j] == dp[i-1][j - weight[i-1]] + price[i-1]){
            j = j - weight[i-1];
            select.push_back(i);
        }
        i--;
    }

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

    int sum = 0;
    for (int i = 0 ; i < select.size() ; i++) sum += weight[select[i] - 1];

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