#include "jelly.h" #include <vector> #include <cstring> #include <algorithm> int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) { const int N = 2e3+10, M = 1e4+10; int ans = 0; int dp1[M], dp2[M]; memset(dp1, 0, sizeof dp1); memset(dp2, 0, sizeof dp2); int n = a.size(); std::vector<std::pair<int, int>> v; for(int i = 0; i < n; ++i) v.push_back({a[i], b[i]}); std::sort(v.begin(), v.end()); for(int i = 0; i < n; ++i) std::tie(a[i], b[i]) = v[i]; for(int i = 0; i < n; ++i){ for(int j = y; j >= b[i]; --j){ dp1[j] = std::max(dp1[j], dp1[j-b[i]]+a[i]); } } for(int i = 0; i < n; ++i){ for(int j = y; j >= b[i]; --j){ dp2[j] = std::max(dp2[j], dp2[j-b[i]]+1); } } int sum = 0; for(int i = 0; i < n; ++i){ sum += a[i]; for(int j = 0; j <= y; ++j){ if(x >= sum-dp1[j]){ ans = std::max(ans, i+1 + dp2[y-j]); } } } return ans; }