#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
using ll = long long;
const ll INF = 1e16;
const int N = 5000 + 5;
ll dp[N][N];
int main() {
cin.tie(0) -> sync_with_stdio(0);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dp[i][j] = INF;
int n; cin >> n;
vector<pair<int,int>> 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(a.begin(), a.end(), [&](pair<int,int> x, pair<int,int> y) {
return x.ff + x.ss < y.ff + y.ss;
});
bool eq = 1;
for (int i = 0; i < n; i++) if (a[i].ff != a[0].ff) eq = 0;
if (eq) {
ll sa = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (sa > a[0].ff) break;
sa += a[i].ss;
cnt++;
}
cout << cnt << "\n";
return 0;
}
a.insert(a.begin(), pair{0, 0});
for (int i = 0; i <= n; i++) dp[i][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i - 1][j];
if (dp[i - 1][j - 1] <= a[i].ff) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + a[i].ss);
}
}
}
int ans = 0;
for (int j = 1; j <= n; j++) {
if (dp[n][j] != INF) ans = j;
}
cout << ans << "\n";
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... |