Submission

Score: 100

User: s0m30n3

Problemset: laracroft

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-18 13:51:22

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,w;
    cin>>n>>w;
    vector<pair<ll, ll>> thing(n+1); 
    for(int i=1;i<=n;i++){
        cin>>thing[i].second;
    }
    for(int i=1;i<=n;i++){
        cin>>thing[i].first;
    }
    // 0/1 Knapsack
    vector<pair<ll,ll>> dp(w+1, {0,0}); // value weight
    for(int i=1;i<=n;i++){
        for(int j=w;j>=thing[i].first;j--){
            ll new_v = dp[j-thing[i].first].first+thing[i].second;
            ll new_w = dp[j-thing[i].first].second+thing[i].first;
            if(new_v>dp[j].first){
                dp[j].first = new_v;
                dp[j].second = new_w;
            }           
            else if(new_v==dp[j].first){
                dp[j].second = min(dp[j].second, new_w);
            }
        }
    }
    cout << dp[w].first << " " << dp[w].second;
}