Editorial for Bedao Regular Contest 18 - LAMPGAME
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Tại mọi thời điểm ~i~, ta chắc chắn chỉ bật ~i~ đèn có giá trị ~B~ lớn nhất. Nhưng lúc đó, ta có thể đã bật nhiều hơn ~i~ bóng đèn từ các thời điểm trước đó. Vì thế, ta sẽ duy trì một Heap để có thể thuận tiện loại bỏ các bóng đèn có các giá trị ~B~ bé nhất để mọi thời điểm ~i~ ta luôn bật không quá ~i~ bóng đèn.
#include <bits/stdc++.h> #define sz(x) (int)x.size() #define pa pair<int, int> #define fi first #define se second using namespace std; const int N = 2e5 + 5; int n; pa a[N]; int main() { cin.tie() -> sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].fi; for (int i = 1; i <= n; i++) cin >> a[i].se; sort(a + 1, a + 1 + n); priority_queue<int, vector<int>, greater<int> > pq; for (int i = 1; i <= n; i++) { if (a[i].fi > sz(pq)) pq.push(a[i].se); else if (pq.top() < a[i].se) { pq.pop(); pq.push(a[i].se); } } long long ans = 0; while (!pq.empty()) ans += pq.top(), pq.pop(); cout << ans; return 0; }
Comments