#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));
vector<vector<int>> dp(n+1, vector<int>(n+1, inf));
for (int i = 0; i <= n; i++) dp[i][0] = 0;
for (int k = 0; k < n; k++){
auto [lim, gain] = a[k];
for (int i = 0; i < n; i++){
dp[k+1][i+1] = dp[k][i+1];
if (dp[k][i] <= lim) dp[k+1][i+1] = min(dp[k+1][i+1], dp[k][i] + gain);
}
}
int ans = 0;
for (int i = 1; i <= n; i++){
if (dp[n][i] >= inf) break;
ans++;
}
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... |