Submission

Score: 100

User: theem1502

Problemset: laracroft

Language: cpp

Time: 0.018 second

Submitted On: 2026-02-17 22:23:49

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

pair<int,int> cmp(pair<int,int> &first, pair<int,int> &second) {
    if (first.first > second.first) {
        return first;
        }
        if (second.first > first.first) {

        return second;
        }
        if (first.second > second.second) {
            return second;

        }
        return first;

}

pair<int,int> recursion(int index, int weight, vector<pair<int,int>> &thearray, vector<vector<pair<int,int>>> &dparray) {
   // cout << "real " << index << " " << weight << "\n";
        if (weight < 0) {
     //   cout << "index " << index << "\n";
        return make_pair(-1*INF, 0);
    }
    if (weight == 0 || index == thearray.size()) {
           // cout << "what " << index << " " << weight << "\n";
        return make_pair(0,0);
    }

    if (dparray[index][weight].first != -1) {
        return dparray[index][weight];
    }

    pair<int,int> firstval = recursion(index + 1, weight - thearray[index].second, thearray, dparray);
    firstval.first += thearray[index].first;
    firstval.second += thearray[index].second;
    pair<int,int> secondval = recursion(index + 1, weight, thearray, dparray);
    //cout << "firstval " << firstval.first << " " <<  firstval.second <<  " " << secondval.first << " " << secondval.second << "\n";
    pair<int,int> val = cmp(firstval, secondval);
  // int sum = max(recursion(index + 1, weight, thearray), recursion(index + 1, weight - thearray[index].second, thearray)+ thearray[index].first);
//    cout << "debug " << index << " " << weight << " " << val.first << " " << val.second << "\n";
    return dparray[index][weight] = make_pair(val.first, val.second);

}


int main() {
    int num, lim;
    cin >> num >> lim;
    vector<pair<int,int>> thearray(num);
    for (int i = 0; i < num; i++) {
        cin >> thearray[i].first;
    }
    for (int i = 0; i < num; i++) {
        cin >> thearray[i].second;

    }
    vector<vector<pair<int,int>>> dp(num+1,vector<pair<int,int>>  (lim+1, make_pair(-1,-1)));
    pair<int,int> the = recursion(0,lim,thearray, dp);
    cout << the.first << " " << the.second;



}