Submission

Score: 100

User: Nathako9n

Problemset: laracroft

Language: cpp

Time: 0.010 second

Submitted On: 2026-01-30 06:08:05

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 500+5,W=5005;
ll dp[N+3][W+3];
int n,w;
int ar[3][N+2];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>w;
    for(int i=1;i<=n;i++)cin>>ar[1][i];
    for(int i=1;i<=n;i++)cin>>ar[2][i];
    int mx=0,in=0;
    for(int i=1;i<=n;i++){
        int x=ar[1][i],y=ar[2][i];
        for(int j=0;j<=w;j++){
            dp[i][j]=dp[i-1][j];
            if(j-y>=0){
                dp[i][j]=max(dp[i][j],dp[i-1][j-y]+x);
                if(dp[i][j]>mx){
                    mx=dp[i][j];
                    in=j;
                }
                if(dp[i][j]==mx&&j<in){
                    in=j;
                }
            }

        }
    }
//    for(int i=n;i>=1;i--){
//        for(int j=w;j>=)
//    }
    cout<<mx<<" "<<in;
    return 0;
}

/*

3 3
1 2 3
4 5 6

6 10
20 5 10 40 15 25
1 2 3 8 7 4




*/