Submission

Score: 100

User: navysrimuang

Problemset: laracroft

Language: cpp

Time: 0.012 second

Submitted On: 2026-03-18 21:48:27

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

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n,x;
	cin >> n >> x;
	vector<int> wt(n+1);
	vector<int> val(n+1);
	vector<vector<pair<ll,ll>>> dp(n+1,vector<pair<ll,ll>>(x+1,{0,0})); // dp[i][x] = at index , and max cap = x, = best val;
	for(int i = 1;i<=n;i++) cin >> val[i];	
	for(int i = 1;i<=n;i++) cin >> wt[i];	

	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=x;j++){
			dp[i][j] = dp[i-1][j];
			if(wt[i] <= j){
				if(dp[i-1][j-wt[i]].first + val[i] > dp[i][j].first){
						dp[i][j].first = dp[i-1][j-wt[i]].first + val[i];
						dp[i][j].second = dp[i-1][j-wt[i]].second + wt[i];
				}else if(dp[i-1][j-wt[i]].first + val[i] == dp[i][j].first){
						dp[i][j].second = min(dp[i][j].second, dp[i-1][j-wt[i]].second + wt[i]);
				}
			}
		}
	}
	
	cout << dp[n][x].first << " " << dp[n][x].second << "\n";	
	
	return 0;
}