Submission

Score: 100

User: devilpoohs

Problemset: laracroft

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-05 20:19:06

#include<bits/stdc++.h>
using namespace std;
const int N=510, MxW=2010;
int g[N],w[N],dp[N][MxW];
int n,W;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>W;
    int dp[W+1];
    for(int i=0;i<=W;i++){
        dp[i]=0;
    }
    for(int i=0;i<n;i++){
        cin>>g[i];
    }
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int we=W;we>=0;we--){
            int ans=INT_MIN;
            if(we-w[i-1]>=0){
                ans=max(ans,g[i-1]+dp[we-w[i-1]]);
            }
            ans=max(ans,dp[we]);
            dp[we]=ans;
        }
    }
    int ans=0;
    for(int we=0;we<=W;we++){
        if(dp[we]==dp[W]){
            ans=we;
            break;
        }
    }

    cout<<dp[W]<<' '<<ans;
    return 0;
}
/*
6 10
20 5 10 40 15 25
1 2 3 8 7 4

3 3
1 2 3
4 5 6

*/