Submission #931454

#TimeUsernameProblemLanguageResultExecution timeMemory
931454vjudge1Gym Badges (NOI22_gymbadges)C++17
24 / 100
131 ms39596 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5+5, S = 2, 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...