Submission #1015723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015723		ByeWorld	Gym Badges (NOI22_gymbadges)	C++14	100 / 100	288 ms	31148 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)/2)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 5e5+10;
const int MAXA = 1e6+10;
const int INF = 1e18+10;
const int INF2 = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmn(int &a, int b){ a = min(a, b); }

int n;
pii a[MAXN];
int dp[MAXN];

signed main(){
    vector <pii> vec;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i].se;
    for(int i=1; i<=n; i++){ cin >> a[i].fi; vec.pb({a[i].fi+a[i].se, i}); }
    vec.pb({-1, -1});
    sort(vec.begin(), vec.end());

    priority_queue <int> pq;
    int tot = 0;

    for(int i=1; i<=n; i++){
        int idx = vec[i].se;
        // cout << idx << ' ' << tot << " pp\n";
        if(tot <= a[idx].fi){
            tot += a[idx].se; pq.push(a[idx].se);
        } else {
            if(pq.top() > a[idx].se){
                tot -= pq.top(); pq.pop();
                tot += a[idx].se; pq.push(a[idx].se);
            }
        }
    }
    cout << pq.size() << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 9 / 9
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49