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.

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

Please read the guidelines before commenting.


There are no comments at the moment.