This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5, S = 10, inf = LLONG_MAX;
int n, x[N], l[N];
pair<int, int> s[N];
map<int, int> dp[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i];
}
bool eq = 1;
for (int i = 0; i < n; i++) {
cin >> l[i];
if (l[i] != l[0]) eq = 0;
}
for (int i = 0; i < n; i++) {
s[i] = make_pair(x[i]+l[i], i);
}
sort(s, s+n);
if (eq) {
int ans = 0;
int lvl = 0;
for (int i = 0; i < n; i++) {
int idx = s[i].second;
if (lvl <= l[idx]) {
ans++;
lvl += x[idx];
}
}
cout << ans << "\n";
}
else {
dp[0][0] = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
auto it = dp[i].end();
while (it != dp[i].begin()) {
if (cnt++ > S) break;
--it;
int j = it->first;
int k = it->second;
auto it2 = dp[i+1].find(j);
if (it2 == dp[i+1].end()) dp[i+1][j] = k;
else it2->second = min(it2->second, k);
if (l[s[i].second] >= k) {
it2 = dp[i+1].find(j+1);
if (it2 == dp[i+1].end()) dp[i+1][j+1] = k + x[s[i].second];
else it2->second = min(it2->second, k + x[s[i].second]);
}
}
dp[i].clear();
}
for (int i = n; i >= 0; i--) {
if (dp[n].find(i) != dp[n].end()) {
cout << i << "\n";
break;
}
}
}
}
# | 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... |