Submission

Score: 100

User: kenmuay

Problemset: laracroft

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-07 22:21:05

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e2+10;
int val[maxn];
int weight[maxn];
int dp[2000+10];



int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int n, w;
    cin >> n >> w;
    
    for(int i=1; i<=n; i++){
        cin >> val[i];
    }
    for(int i=1; i<=n; i++){
        cin >> weight[i];
        
    }
    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;

    for(int i=1; i<=n; i++){
        for(int j=w; j>=0; j--){
            if(j-weight[i] < 0) break;
            if(dp[j-weight[i]] == -0x3f) continue;
            dp[j] = max(dp[j-weight[i]]+val[i], dp[j]);
        }
    }
    int mx=0;
    int idx=1e9+7;
    for(int i=1; i<=w; i++){
        if(dp[i] == mx) {
            idx = min(idx, i);
        }
        if(dp[i] > mx){
            mx = max(mx, dp[i]);
            idx = i;
        } 
    }
    if(idx == 1e9+7) idx = 0;
    cout << mx << ' ' << idx ;
}