Submission #1171036

#TimeUsernameProblemLanguageResultExecution timeMemory
1171036qrnGym Badges (NOI22_gymbadges)C++20
100 / 100
148 ms23928 KiB
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 2e5 + 5;
const intt L = 21;


void solve() {
    intt n;
    cin >> n;
    vector<intt> x(n), l(n);
    for(intt i = 0; i < n; i++) {
        cin >> x[i];
    }
    for(intt i = 0; i < n; i++) {
        cin >> l[i];
    }

    vector<pair<intt,intt>> v;
    for(intt i = 0; i < n; i++) {
        v.pb({x[i] + l[i], i});
    }
    sort(ALL(v));

    priority_queue<intt> pq;
    intt st = 0;;
    for(auto u : v) {
        intt idx = u.se;
        if(st <= l[idx]) {
            st += x[idx];
            pq.push(x[idx]);
        } else {
            if(pq.top() <= x[idx]) continue;
            st -= pq.top();
            pq.pop();
            st += x[idx];
            pq.push(x[idx]);
        }
    }
    cout << pq.size() << endl;
}

signed main() {
    SPEED;
    intt tst = 1;
    while (tst--) {
        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...