Submission #1321060

#TimeUsernameProblemLanguageResultExecution timeMemory
1321060yonatanlGym Badges (NOI22_gymbadges)C++20
100 / 100
390 ms40068 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> #define rep(i, s, e) for (ll i = s; i < e; i++) #define upmin(a, b) a = min(a, b) #define upmax(a, b) a = max(a, b) using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using pll = pair<ll, ll>; using vpll = vector<pll>; const ll INF = 1e18; void solve() { ll n; cin >> n; vll l(n), r(n); rep(i, 0, n) cin >> l[i]; rep(i, 0, n) cin >> r[i]; vpll arr(n); rep(i, 0, n) { arr[i] = { r[i] + l[i], l[i] }; } sort(arr.begin(), arr.end()); multiset<ll> s; s.insert(arr[0].second); ll curSum = arr[0].second; rep(i, 1, n) { ll curR = arr[i].first - arr[i].second; ll curL = arr[i].second; if (curR >= curSum) { curSum += curL; s.insert(curL); } else if (curR < curSum && *(--s.end()) > curL) { curSum -= *(--s.end()); s.erase(--s.end()); curSum += curL; s.insert(curL); } } cout << s.size() << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...