Submission #886530

#TimeUsernameProblemLanguageResultExecution timeMemory
886530vjudge1Gym Badges (NOI22_gymbadges)C++17
51 / 100
2039 ms30016 KiB
#include <bits/stdc++.h> using namespace std; #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define sp " " #define endl "\n" #define pb push_back #define pii pair<int, int> #define st first #define nd second #define N 500005 #define int long long const int INF = 1e9 + 7; int x[N], l[N]; int32_t main(){ //fileio(); fastio(); int n; cin>>n; for (int i = 1; i <= n; i++){ cin>>x[i]; } for (int i = 1; i <= n; i++){ cin>>l[i]; } vector<int> v(n, 0); iota(v.begin(), v.end(), 1); sort(v.begin(), v.end(), [&](int a, int b){ if (x[a] == x[b]) return l[a] < l[b]; return x[a] < x[b]; }); int sum = 0; int ans = 0; multiset<pii> maks; for (auto i : v){ if (sum <= l[i]){ sum += x[i]; ans++; maks.insert({l[i] + x[i], x[i]}); continue; } int tmp = 0; auto it = maks.rbegin(); while(it != maks.rend() && it->st + tmp >= sum + x[i]){ tmp += it->nd; it++; if (sum <= l[i] + tmp){ sum += x[i]; ans++; maks.insert({l[i] + x[i], x[i]}); break; } } } //cout<<endl; cout<<ans<<endl; cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...