#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; for (int i = 1; i <= n; i++) { v.emplace_back(a[i], b[i]); } sort(v.begin(), v.end()); if (x > y) swap(x, y); vector <pair <int, int>> dp(x + 1); for (int i = 0; i < n; i++) { auto [aa, bb] = v[i]; for (int j = aa; j <= x; j++) { dp[j] = max(dp[j], {dp[j - aa].first + 1, i}); } } pair <int, int> mx = {0, 0}; for (int i = 0; i <= x; i++) { mx = max(mx, {dp[i].first, i}); } int cur = dp[mx.second].second; int xx = mx.first; vector <bool> visited(n + 1); while (!visited[cur]) { visited[cur] = true; cur = dp[xx - v[cur].first].second; xx -= v[cur].first; } int ans = count(visited.begin(), visited.end(), true); for (int i = 0; i < n; i++) { if (visited[i]) continue; if (y >= v[i].first) ans++, y -= v[i].first; } 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 again sub 5: a and b are same */