Submission

Score: 100

User: njoop

Problemset: laracroft

Language: cpp

Time: 0.011 second

Submitted On: 2025-04-04 02:26:38

//int mx, weight;
//void sol(int v[], int w[], int idx, int n, int val, int we, int W){
//	if(we > W) return;
//	if(idx >= n){
//		if(val > mx){
//			mx = val;
//			weight = we;
//		}
//		return;
//	}
//	sol(v,w,idx+1,n,val,we,W);
//	sol(v,w,idx+1,n,val+v[idx],we+w[idx],W);
//}
//
//main(){
//	sol(v,w,0,n,0,0,W);
//	cout<<mx<<' '<<weight;
//}
#include <bits/stdc++.h>
#define int long long
using namespace std;
int x, y;
int32_t main(){
	int n, W;
	cin>>n>>W;
	int dp[n+1][W+1];
	int wt[n], val[n];
	for(int i=0;i<n;i++) cin>>val[i];
	for(int i=0;i<n;i++) cin>>wt[i];
	int i, w;
	for (i = 0; i <= n; i++) {
		for (w = 0; w <= W; w++) {
			if (i == 0 || w == 0) dp[i][w] = 0;
			else if (wt[i - 1] <= w) dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
			else dp[i][w] = dp[i-1][w];
			if(x != dp[i][w]){
				x = dp[i][w];
				y = w;
			}
		}
	}
	
	cout<<x<<' '<<y;
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=W;j++){
//			cout<<dp[i][j]<<' ';
//		}cout<<endl;
//	}
}
/*
3 3
1 2 3
4 5 6
*/