#include <bits/stdc++.h> #include "jelly.h" using namespace std; // testuje cos tylko i tak to juz wbilem int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) { int n = (int)a.size(); // items: (b_i, a_i) - sortujemy po cenie w sklepie B vector<pair<int,int>> items(n); for (int i = 0; i < n; i++) { items[i] = {b[i], a[i]}; } sort(items.begin(), items.end()); // preB[k] = koszt kupienia pierwszych k elementów w sklepie B vector<long long> preB(n + 1, 0); for (int i = 0; i < n; i++) { preB[i + 1] = preB[i] + items[i].first; } const int INF = 1e9; // dp[c] = minimalny koszt w sklepie A, aby kupić dokładnie c smaków z aktualnego sufiksu vector<int> dp(n + 1, INF); dp[0] = 0; // max_items[k] = maksymalna liczba smaków z items[k:] możliwa do kupienia w sklepie A za budżet x vector<int> max_items(n + 1, 0); max_items[n] = 0; // Przetwarzamy od końca: dla każdego k chcemy znać "ile da się wziąć z sufiksu w A" for (int j = n - 1; j >= 0; j--) { int a_val = items[j].second; // 0/1 knapsack - aktualizacja dp wstecz for (int c = n; c >= 1; c--) { if (dp[c - 1] != INF) { dp[c] = min(dp[c], dp[c - 1] + a_val); } } // wyznacz maksymalną liczbę elementów z sufiksu [j..n-1], którą da się kupić w A int max_c = 0; int limit = n - j; for (int c = 0; c <= limit; c++) { if (dp[c] <= x) max_c = c; } max_items[j] = max_c; } // Próbujemy wszystkich podziałów: // - pierwsze k (najtańsze w B) kupujemy w B // - resztę wybieramy optymalnie w A z sufiksu items[k:] int ans = 0; for (int k = 0; k <= n; k++) { if (preB[k] <= (long long)y) { ans = max(ans, k + max_items[k]); } } return ans; }