Submission

Score: 100

User: kimza

Problemset: laracroft

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-09 22:12:02

#include <bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    int p[n+1], w[n+1];
    p[0] = 0;
    w[0] = 0;
    // vector<int> w;
    for(int i=1;i<=n;i++){
        cin >> p[i];
    }
    for(int i=1;i<=n;i++){
        cin >> w[i];
    }   
    // for(int x:w) cout << x << " ";
    // cout << "\n";

    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j-w[i]<0){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
            }
            
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(auto& x:dp[i]){
    //         cout << x << " ";
    //     }
    //     cout << "\n";
    // }
    int fidx = 0;
    for(int i=0;i<=m;i++){
        if(dp[n][i]==dp[n][m]){
            fidx = i;
            break;
        }
    }
    cout << dp[n][m] << " " << fidx;
    return 0;
}