Submission

Score: 100

User: raidina

Problemset: laracroft

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-08 00:42:19

#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;

const int N = 501;
int n,m,cost[N],w[N],dp[N][2001],mx=INT_MIN,cnt=INT_MAX;

int main(){
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        cin >> cost[i];
    }
    for(int i = 1;i<=n;i++){
        cin >> w[i];
    }

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(w[i]<=j) dp[i][j] = max(dp[i-1][j-w[i]]+cost[i],dp[i-1][j]);
            else dp[i][j]=max(dp[i][j],dp[i-1][j]);

            if(mx<dp[i][j] && dp[i][j]!=0){
                mx=dp[i][j];
                cnt=j;
            }
            else if(mx == dp[i][j] && j < cnt && cnt != INT_MIN && dp[i][j]!=0){
                mx=dp[i][j];
                cnt=j;
            }
        }

    }

    // for(int i = 0;i<=n;i++){
    //     for(int j = 0;j<=m;j++){
    //         cout << dp[i][j] << ' ';
    //     }cout << '\n';
    // }
    if(mx == INT_MIN && cnt == INT_MAX){
        mx=0;
        cnt=0;
    }
    cout << mx << ' ' << cnt;

}