So, here’s my code for SOLVEMORE from STARTERS 78.
This is the basic idea of what I’m doing.
Take sum of ai and bi, store it in ci {si, i}. ci is a vector of pair<ll, int>, which stores sum and index.
Then, sort c.
Find cumulative sum for c.
Using std::upper_bound, find idx for which ci > k.
Now, we find if there is an ai, which when added to ci-1 <=k
We do this by adding ci.second, that is original indices involved, and are part of problems solved to a set.
We iterate over a, if there’s an a s.t c[idx-1] + a[i] <= k and i is not in set, then we increase our answer.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int t;
cin >> t;
while (t--) {
ll n, k, i;
cin >> n >> k;
vector<ll> a(n), b(n);
vector<pair<ll, int>> c(n);
for (i = 0; i < n; i++) cin >> a[i];
for (i = 0; i < n; i++) {
cin >> b[i];
c[i].first = a[i] + b[i];
c[i].second = i;
}
sort(c.begin(), c.end());
for (i = 1; i < n; i++) c[i].first += c[i - 1].first;
auto idx = distance(c.begin(),
upper_bound(c.begin(), c.end(), make_pair(k, INT_MIN)));
unordered_set<int> us;
for (i = 0; i < idx; i++) {
us.emplace(c[i].second);
}
ll ans = idx;
if (idx - 1 >= 0) {
for (i = 0; i < n; i++) {
if (!us.count(i) && a[i] + c[idx - 1].first <= k) {
ans++;
break;
}
}
}
std::cout << ans << endl;
}
return 0;
}