Submission #1275255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275255		danieldcv	Gym Badges (NOI22_gymbadges)	C++20	100 / 100	139 ms	16400 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef set<int> si;
typedef map<int, int> mii;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define rep(i, a, b) for(int i = a; i < b; i++)
#define sz(x) (int)x.size()
#define pc __builtin_popcountll
#define msb(x) 31 - __builtin_clz(x)
#define lsb(x) __builtin_ctz(x)
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;
const int MOD = 1e9 + 7;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
/* 

*/
 
void solve() {
    int n; cin >> n;
    vi x(n), l(n);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < n; i++) cin >> l[i];
    vi id(n); iota(all(id), 0);
    
    auto cmp = [&] (int a, int b) {
        return x[a] + l[a] < x[b] + l[b];
    };

    sort(all(id), cmp);
    priority_queue<int> pq;
    int sum = 0;
    int ans = 0;
    for (int j = 0; j < n; j++) {
        int i = id[j];
        if (sum <= l[i]) {
            sum += x[i]; pq.push(x[i]);
            ans++;
        }
        else if (x[i] < pq.top() && sum - pq.top() <= l[i]) {
            sum -= pq.top(); pq.pop();
            sum += x[i]; pq.push(x[i]);
        }
    }
    cout << ans << '\n';
}
 
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // int t; cin >> t; while (t--) solve();
    solve();
    return 0;
}

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