#include <bits/stdc++.h> #include "jelly.h" using namespace std; int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) { int n = a.size(); reverse(a.begin(), a.end()); a.emplace_back(0); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); b.emplace_back(0); reverse(b.begin(), b.end()); vector <pair <int, int>> v; v.emplace_back(-1, -1); for (int i = 1; i <= n; i++) { v.emplace_back(a[i], b[i]); } sort(v.begin(), v.end(), [](const pair <int, int> &aa, const pair <int, int> &bb){ if (aa.second == bb.second) return aa.first < bb.first; else return aa.second < bb.second; }); bool dp[10005] = {0}; dp[0] = true; int ysum[10005] = {0}; int sum = 0; int ans = 0; for (int i = 1; i <= n; i++) { auto [aa, bb] = v[i]; sum += bb; for (int j = 10000; j >= aa; j--) { if (dp[j - aa]) { dp[j] = true; ysum[j] = max(ysum[j], ysum[j - aa] + bb); } } for (int j = 10000; j >= 0; j--) { if (dp[j] && j <= x && (sum - ysum[j]) <= y) { ans = i; break; } } } return ans; } /* sub 1-2 , 3: constraints , y = 0 dp[i][j][k] = max ans when we used i at a, j at b, checked up to k answer is at dp[x][y][n] sub 4: b is all equal greedy stupid sub 5: a and b are same knapsack, if can separate into two piles then ok */