#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()
const int inf = 1e16;
int32_t main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
vector<pii> a(n);
for (int i = 0; i < n; i++) cin >> a[i].ss;
for (int i = 0; i < n; i++) cin >> a[i].ff;
sort(entire(a), [&](pii x, pii y){
return (x.ff + x.ss < y.ff + y.ss);
});
vector<int> dp(n+1, inf); dp[0] = 0;
for (auto [lim, gain] : a){
vector<int> dpnew = dp;
for (int i = 0; i < n; i++){
if (dp[i] > lim) continue;
dpnew[i+1] = min(dpnew[i+1], dp[i] + gain);
}
dp = dpnew;
}
int ans = 0;
for (int i = 1; i <= n; i++){
if (dp[i] >= inf) continue;
ans = i;
}
cout << ans << endl;
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |